首页 > 代码库 > 求质数两个方法的好坏分析(是否易懂，操作次数，运算复杂度时间)
求质数两个方法的好坏分析(是否易懂，操作次数，运算复杂度时间)
方法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 }
求质数两个方法的好坏分析(是否易懂，操作次数，运算复杂度时间)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。