1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
#include<iostream>
#include<windows.h>
#include<time.h>
using  namespace  std;
 
//声明素数表的数组为全局变量
int  a[10000]={2,0}; //素数表初始化
int  flagnumber=0; //记录素数表中的个数
int  minnumber=0;
int  maxnumber=0;
//一般来说需要声明将要调用的函数
int  Simple_count( int  a, int  b); //累除法
int  numlist( int  a[]) //建立素数表
{
  
  int  flag=0; //确定数组当前存储素数的位置
  bool  repeat= true ; //循环标志位设定
  int  j=0;
  for ( int  i=2;i<10000;i++) //将通过设定i的上限来扩大搜索的范围
  {
   
   while (repeat)
   {
    if ((j==flag)&&(i%a[flag]!=0)) //判断是否已经到了当前素数表的最后一个元素，还不能整除的，把当前数字推入素数表
    {
     repeat= false ;
     flag++;
     a[flag]=i;
    }
    else
    {
     if (i%a[j]==0) //如果能整除跳出while语句
     {
      repeat= false ;
     }
     else //否则继续判断
     {
      j++;
     }
    }
   }
   repeat= true ; //i每进行一次测试前，必须置值为真
   j=0; //下一个数的除数应该从a[0]开始，所以j应该置零
  }
  return  flag; //返回计算的个数
  //其实有可能出现误差，如果这个含有最大约数的数还有一个很大的素数因子没有检测出来
  //又或者有一个数由于其素数公因子太多，因此少计算进去，可能存在误差
  //但是从另一方面考虑，如果这个数真的含有最多的约数，那么它的素数公因子必须很小
  //因此，出错的概率必须和a和b之间存在的个数有关
}
DWORD  WINAPI test( LPVOID  pParam)
{
  int  jump=0;
  *(( int *)pParam)=jump;
  
     bool  repeat= true ;
  int  testnumber=minnumber; //存储含有最大约数的数，以备检查（利用累除法检查）
  int  numberflag=0; //设置比较位
  int  statist=1; //到底应该设置统计值为多少需要分析 
  int  b[10000]={0}; //初始化当前标志位记载有多少个这样相同的素数，并且初始化
  int  j=0; //保存指向标志位数组的当前光标
  int  temp=0; //循环除法的载体
  for ( int  i=jump;i<=maxnumber;i=i+2)
  {
   //j不能否超越flag的存在
   for ( j=0;i>=a[j];j++) //不能超过素数表的界限，但是必须排除这个数小于10000，当这个数很小时，没有必要比较下去 
   {
    if (j>flagnumber) //当超出素数表的范围就表示已经遍历完素数表的所有的元素
    {
     break ;
    }
    else
    {
     temp=i;
     while (temp%a[j]==0) //如果能够整除，标志位加1，同时记得除去已经添加的次数
     {
      b[j]++;
      //记住a和b的下标是对应的
      temp=temp/a[j];
     }
    }
   }
   //现在统计这个数含有的公因子个数
   for ( int  k=0;k<=j;k++)
   {
    if (b[k]!=0)
    {
     statist=statist*(b[k]+1);
     
    }
    
   }
  
   if (numberflag<statist) //取其中最大的数字
   {
    numberflag=statist;
    testnumber=i;
    
   }
   statist=1; //重置
   for ( k=0;k<=j;k++)
   {
    b[k]=0;  
   }
  }
  
  cout<< "使用素数表的方法获得的最大约数个数是:" <<numberflag<<endl;
  jump=numberflag;
  return  0;
}
 
int  Simple_count( int  a, int  b) //当a和b之间的个数在50左右时，可以直接使用类除法（通过计算测试时间表明
{ //当a的值大于100000000时，每计算一个数，需要花费接近1s的时间，意昧着：计算10万个数需要半小时
  int  number=0; //统计约数的个数
  int  flag=0; //设置比较数，当后一个数的约数个数大于前一个数时，重置
  
  for ( int  i=a;i<=b;i++) //外层循环从a到b
  {
   for ( int  j=1;j<=i/2;j=j+1) //内层循环检测从2到自身
   {
    
    if (i%j==0)
    {
     number++;
    }
   }
   number++; //自身也是一个约数，需添加进去
   if (number>flag) //重置标志位
   {
    flag=number;
   }
   number=0; //刚才忘记恢复计数值为0
  }
  return  flag;
}
int  main()
{
  clock_t  start,finish;
  start= clock ();
     HANDLE  hHandle[2];
  int  handleresult1,handleresult2;
  flagnumber=numlist(a); //获得当前的素数表，还有当前素数表的个数flag+1，表示当前素数表从0开始
  cout<<flagnumber<<endl;
  cout<<a[1000]<<endl;
  
     int  result; //获取当前的结果
  cout<< "请输入两个数，以便获取当前的范围" ;
  cout<<endl;
  cin>>minnumber>>maxnumber;
  handleresult1=minnumber;
  handleresult2=minnumber+1;
  if (maxnumber-minnumber<50)
  {
   result=Simple_count(minnumber,maxnumber);
  }
  else
  {
   hHandle[0]=CreateThread(NULL,0,
    test,( void *)(&handleresult1),0,NULL);
   hHandle[1]=CreateThread(NULL,0,
    test,( void *)(&handleresult2),0,NULL);
  }
     WaitForMultipleObjects(2,hHandle,TRUE,INFINITE);
  finish= clock ();
  cout<< "the time has been used :" <<finish-start<<endl;
  return  0;
}