首页 > 代码库 > 求质数两个方法的好坏分析(是否易懂,操作次数,运算复杂度时间)

求质数两个方法的好坏分析(是否易懂,操作次数,运算复杂度时间)

 方法1:
 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include <malloc.h>
 4 #include <stdbool.h>
 5 
 6 int main()
 7 {
 8     long i,j,n,ans=0;
 9     //vis[x]若为true,则代表质数,若为false,则不是质数
10     bool *vis=(bool *) malloc (sizeof(bool)*100000001);
11     long *zhi=(long *) malloc (sizeof(long)*10000000);
12     scanf("%ld",&n);
13     for (i=2;i<=n;i++)
14         vis[i]=true;
15     for (i=2;i<=n;i++)
16         if (vis[i])
17         {
18             ans++;
19             zhi[ans]=i;
20             //若大于i的数能被i整除,则该数不是质数
21             for (j=i;j<=n;j+=i)
22                 vis[j]=false;
23         }
24     printf("%ld\n",ans);
25     return 0;
26 }

 方法2:

    

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 
 4 //判断i是否质数,需要判断i能否被(long)sqrt(i)以内的数整除
 5 //若i能被其中一个质数整除,则i不是质数;否则i是质数
 6 
 7 int main()
 8 {
 9     //n=10 ans=4
10     //n=100 ans=25
11     //n=1000 ans=168
12     //n=10000 ans=1229
13     //n=100000 ans=9592
14     //n=1000000 ans=78498
15     //n=10000000 ans=664579
16     //n=100000000 ans=5761455
17     long i,j,n,flag,ans=1,t=1;
18     long *zhi=(long *) malloc (sizeof(long)*10000000);
19     scanf("%ld",&n);
20     zhi[0]=2;
21     for (i=3;i<=n;i++)
22     {
23         //若"zhi[t]*zhi[t]==i"成立,则i不是质数,不用继续判断
24         //且大于i的数需要用zhi[t]判断(j=0;j<t+1;j++)
25         //这个方法比"当质数大于(long)sqrt(i)时退出"速度快
26         //而(zhi[t]-1)*(zhi[t]-1)<=i<=n
27         //当i小于longint范围都能实现
28         if (zhi[t]*zhi[t]==i)
29         {
30             t++;
31             continue;
32         }
33         flag=1;
34         for (j=0;j<t;j++)
35             if (i%zhi[j]==0)
36             {
37                 flag=0;
38                 break;
39             }
40         if (flag)
41         {
42             zhi[ans]=i;
43             ans++;
44         }
45     }
46     printf("ans=%ld\n",ans);
47     /*
48     for (i=0;i<ans;i++)
49         printf("%ld ",zhi[i]);
50     printf("\n");
51     */
52     /*
53     if (zhi[ans]==n)
54         printf("%ld is a prime\n",n);
55     else
56         printf("%ld is not a prime\n",n);
57     */
58     return 0;
59 }

 

 

方法1中,所有被n以内素数(2,3,5,…)整除的 小于等于n的数,都被标记为非素数。

如: 2——4,6,…… false    (n/2个)

     3——6,9,…… false  (n/3个)

        ……

技术分享

 

 

 

其中k为小于等于n的最大的素数,r为欧拉常数,约为0.5772。

即该方法的时间复杂度为n*log(n),实际上远小于此。

N

100

1000

10000

10,0000

100,0000

1000,0000

1,0000,0000

Log(n)

4.61

6.91

9.21

11.51

13.82

16.12

18.42

部分操作次数

196

2294

25529

275992

2932206

30794896

320798736

运行时间

 

 

 

 

15ms

218ms

2937ms

 

 

方法2中,n以内的每个数k通过判断能否被sqrt(k)以内的质数整除来判断能否为质数

N

100

1000

10000

10,0000

100,0000

1000,0000

1,0000,0000

Log(n)

4.61

6.91

9.21

11.51

13.82

16.12

18.42

部分操作次数

292

3892

54632

851818

14991536

296709390

6425932861

运行时间

 

 

 

 

46ms

906ms

19435ms

 

相比起方法2,方法1编写更简易明了,而程序的计算更简单很多(方法2的运算是%,*,而方法1的运算是+),运算次数也更很多,所以运行时间也短很多。综上所述求质数方法1更优。

 

调试程序:

 

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include <malloc.h>
 4 #include <stdbool.h>
 5 #include <time.h>
 6 
 7 int main()
 8 {
 9     clock_t start,finish;
10     start=clock();
11     //long long total=0;
12     long i,j,n=100000000,ans=0;
13     //vis[x]若为true,则代表质数,若为false,则不是质数
14     bool *vis=(bool *) malloc (sizeof(bool)*100000001);
15     long *zhi=(long *) malloc (sizeof(long)*10000000);
16     //scanf("%ld",&n);
17     for (i=2;i<=n;i++)
18         vis[i]=true;
19     for (i=2;i<=n;i++)
20         if (vis[i])
21         {
22             ans++;
23             zhi[ans]=i;
24             //若大于i的数能被i整除,则该数不是质数
25             for (j=i;j<=n;j+=i)
26                 vis[j]=false;
27             //total=total+n/i+1;
28         }
29     printf("%ld\n",ans);
30     //printf("total=%lld\n",total);
31     finish=clock();
32     printf("time=%.lfms\n",(double)(finish-start));
33     return 0;
34 }

 

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 
 4 //判断i是否质数,需要判断i能否被(long)sqrt(i)以内的数整除
 5 //若i能被其中一个质数整除,则i不是质数;否则i是质数
 6 
 7 int main()
 8 {
 9     //n=10 ans=4
10     //n=100 ans=25
11     //n=1000 ans=168
12     //n=10000 ans=1229
13     //n=100000 ans=9592
14     //n=1000000 ans=78498
15     //n=10000000 ans=664579
16     //n=100000000 ans=5761455
17     long i,j,n,flag,ans=1,t=1;
18     long *zhi=(long *) malloc (sizeof(long)*10000000);
19     scanf("%ld",&n);
20     zhi[0]=2;
21     for (i=3;i<=n;i++)
22     {
23         //若"zhi[t]*zhi[t]==i"成立,则i不是质数,不用继续判断
24         //且大于i的数需要用zhi[t]判断(j=0;j<t+1;j++)
25         //这个方法比"当质数大于(long)sqrt(i)时退出"速度快
26         //而(zhi[t]-1)*(zhi[t]-1)<=i<=n
27         //当i小于longint范围都能实现
28         if (zhi[t]*zhi[t]==i)
29         {
30             t++;
31             continue;
32         }
33         flag=1;
34         for (j=0;j<t;j++)
35             if (i%zhi[j]==0)
36             {
37                 flag=0;
38                 break;
39             }
40         if (flag)
41         {
42             zhi[ans]=i;
43             ans++;
44         }
45     }
46     printf("ans=%ld\n",ans);
47     /*
48     for (i=0;i<ans;i++)
49         printf("%ld ",zhi[i]);
50     printf("\n");
51     */
52     /*
53     if (zhi[ans]==n)
54         printf("%ld is a prime\n",n);
55     else
56         printf("%ld is not a prime\n",n);
57     */
58     return 0;
59 }

 

求质数两个方法的好坏分析(是否易懂,操作次数,运算复杂度时间)