遍历模除质数筛选法

2019-04-14 15:22发布

站内文章 / 模拟电子
15119 0 1217
#include #include #include /** 算法逻辑解析：一个数a除以a前边所有的质数都除不尽，则a也为质数。 此例中，Prime[]数组存放已确认的质数，偶数跳过，直接确认奇数是否为质数。 易错点：核心逻辑是a于Prime[]数组中已存在的数都要判断，都除不尽a才是质数， 有一个除不尽，就是合数，就要a+2,并且，Prime[]要回到第一个元素。 另外，代码中有两个if()break不得不加上，解决了边界问题。 **/ unsigned int prime(int *Prime,unsigned int N,unsigned long long int* sum) { unsigned int i,j,k; for(i=5,j=1;i<=N;i+=2) { k=j; j=1; while(j<=k) { if(0==i%Prime[j]) {/************************/// printf("●●");//打印合数“*” if(i>N) //如果超出了不break，while会找到N之外的第一个质数,并由for退出循环。 break; i+=2; j=1; //i回到1,回到数组第一个元素 } else j++; } if(i>N) //加上break,防止由while返回已经超出了N的i进入数组。i=上一个奇数+2 break; //如果把Prime[j]=i;放到while上边意图减少一个break语句，但是for循环一进来会产生更多的麻烦 Prime[j]=i; /****************/// printf(" ●");//打印质数“ ” *sum=*sum+i; } return k+1; } //void prime int main(int argc,char *argv[]) { unsigned int N=1000000;/** N要>=100,1~100的质数密度是25%。**/ int* Prime=(int*)malloc(N/4*sizeof(unsigned int)); Prime[0]=2; Prime[1]=3; unsigned long long int sum=Prime[0]+Prime[1]; printf("别动，请耐性等待程序执行... "); clock_t before=clock(); //获取系统时间 unsigned int a=prime(Prime,N,&sum); clock_t after=clock(); //获取系统时间 printf("%lu 以内有 %lu 个质数。之和为：%llu。 计算用时为 %d 毫秒。",N,a,sum,after-before); free(Prime); return 0; } //int main

热门文章