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

IT/互联网 / 编程语言 养生小编 来源:互联网 168浏览 0评论

 方法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("%ldn",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=410     //n=100 ans=2511     //n=1000 ans=16812     //n=10000 ans=122913     //n=100000 ans=959214     //n=1000000 ans=7849815     //n=10000000 ans=66457916     //n=100000000 ans=576145517     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<=n27         //当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=%ldn",ans);47     52     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("%ldn",ans);30     //printf("total=%lldn",total);31     finish=clock();32     printf("time=%.lfmsn",(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=410     //n=100 ans=2511     //n=1000 ans=16812     //n=10000 ans=122913     //n=100000 ans=959214     //n=1000000 ans=7849815     //n=10000000 ans=66457916     //n=100000000 ans=576145517     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<=n27         //当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=%ldn",ans);47     52     58     return 0;59 }

 

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

原文:http://www.cnblogs.com/cmyg/p/6623558.html