宁波网站优化公司哪家好,建设主管部门门户网站,常州外贸网站建设,Wordpress的未来求n以内的素数#xff0c;可以用试除法或者埃拉托斯特尼筛法#xff08;埃氏筛法#xff09; 文章目录 试除法埃拉托斯特尼筛法#xff08;埃氏筛法#xff09;两种方法测试运行效率 输入#xff1a;数字n 输出#xff1a;n以内所有的素数
不管是哪个方法#xff0c;都… 求n以内的素数可以用试除法或者埃拉托斯特尼筛法埃氏筛法 文章目录 试除法埃拉托斯特尼筛法埃氏筛法两种方法测试运行效率 输入数字n 输出n以内所有的素数
不管是哪个方法都有一个数学结论可以减少循环次数
如果有一个数不是质数那么它至少有一个因子小于等于他的平方根。所以说n有因数的话一定有一个小于根号n因此只需要看遍历到根号n即可。 反过来说如果根号n内没有某个数的因数那么整个2n-1都没有这个数的因数。
试除法
使用i*i而不是sqrt(n)是为了避免对浮点数进行处理。
/**
* 试除法
* 0、1 都不是质数
* 如果有一个数不是质数那么它至少有一个因子小于等于他的平方根
* 算法效率从n变为根号n
*/
int isPrime(int n){if(n2) {return 0;}for(int i2;i*in;i){if(n%i0){return 0;}}return 1;
}
void findPrimesByTrialDivision(int n){for (int i 2; i n; i) {if (isPrime(i)) {printf(%d\t, i);}}printf(\n);
}埃拉托斯特尼筛法埃氏筛法
质数的倍数一定是非质数。从而逐步将非质数排除。 由于如果有一个数不是质数那么它至少有一个因子小于等于他的平方根。 所以外层循环从2-根号n内层循环从i*i开始。
void Eratosthenes(int n){int *isPrime calloc(n1,sizeof(int));for(int i2;in;i){// 初始化所有数都是质数isPrime[i] 1;}for(int i2; i*in;i){if(isPrime[i]){for(int ji*i;jn;ji){isPrime[j] 0;}}}for (int i 2; i n; i) {if (isPrime[i]1) {printf(%d\t, i);}}printf(\n);
}两种方法测试
int main(){int n20;Eratosthenes(n);findPrimesByTrialDivision(n);return 0;
}运行效率
我们把打印质数的代码删掉打印下运行时间
int main() {int n 6000000;start clock();Eratosthenes(n);finish clock();time1 (double) (finish - start) / CLOCKS_PER_SEC;printf(埃氏筛法所用时间: %f\n, time1);start clock();findPrimesByTrialDivision(n);finish clock();time2 (double) (finish - start) / CLOCKS_PER_SEC;printf(试除法所用时间: %f\n, time2);return 0;
}可以看到埃氏筛法确实在数据量大的的时候效率更高。
