C语言--求n以内的素数（质数）

求n以内的素数，可以用试除法或者埃拉托斯特尼筛法（埃氏筛法）

输入：数字n
输出：n以内所有的素数

不管是哪个方法，都有一个数学结论可以减少循环次数：

如果有一个数不是质数，那么它至少有一个因子小于等于他的平方根。所以说n有因数的话，一定有一个小于根号n，因此只需要看遍历到根号n即可。
反过来说，如果根号n内没有某个数的因数，那么整个2，n-1都没有这个数的因数。

试除法

使用i*i而不是sqrt(n)是为了避免对浮点数进行处理。

/**
*  试除法
*  0、1 都不是质数
*  如果有一个数不是质数，那么它至少有一个因子小于等于他的平方根
*  算法效率从n变为根号n
*/
int isPrime(int n){if(n<2) {return 0;}for(int i=2;i*i<=n;i++){if(n%i==0){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(n+1,sizeof(int));for(int i=2;i<=n;i++){// 初始化所有数都是质数isPrime[i] = 1;}for(int i=2; i*i<=n;i++){if(isPrime[i]){for(int j=i*i;j<=n;j+=i){isPrime[j] = 0;}}}for (int i = 2; i <= n; i++) {if (isPrime[i]==1) {printf("%d\t", i);}}printf("\n");
}

两种方法测试

int main(){int n=20;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;
}

可以看到埃氏筛法确实在数据量大的的时候效率更高。