求素数的筛法（暴力和筛法求100以内的素数）

素数是指除1以外只能被1和自身整除的整数。

1 从定义出发的暴力法

#include <stdio.h> bool isPrime(int n) { int ret = 0; for(int i=1;i<=n;i ) // 边界为[1,n] { if(n%i == 0) ret ; } if(ret == 2) return true; return false; } int main() { for(int i=1;i<100;i ) if(isPrime(i)) printf("%d ",i); getchar(); }

2 暴力结合枚举和边界

#include <stdio.h> double sqrt(double x,double y) { if(y*y-x<-1e-5 || y*y-x > 1e-5) return sqrt(x,(y x/y)/2.0); else return y; } bool isPrime(int n) { if(n<2) return false; if(n==2) return true; if(n%2==0) return false; int limit = sqrt(n,n/2) 1; for(int i=3;i<limit;i =2) if(n%i==0) return false; return true; } void prime(int n) { for(int i = 2;i<n 1;i ) if(isPrime(i)) printf("M ",i); } int main() { prime(1000); getchar(); }

3 埃拉托斯特尼素数筛法

素数筛法的思路是：从2开始，不包括2本身，其倍数全部筛掉，剩下的全是素数。

先是筛2的倍数，筛完后剩下的最小整数是3，然后筛3的倍数；

然后筛5的倍数……

demo code:

#include <stdio.h> #include <math.h> #include <string.h> #include <malloc.h> #define N 100 void prime(int n) { int *arr = (int*)malloc(sizeof(int)*(n 1)); memset(arr,0,sizeof(int)*(n 1));// arr[i]==0表示i是素数 arr[1] = 1; int m = sqrt(n) 1; for(int i=2;i<m;i ) if(arr[i]==0) for(int j=i*2; j<=n; j =i) arr[j] = 1; for(i=1;i<=n;i ) if(arr[i]==0) printf("M ",i); } int main() { prime(10000); getchar(); }

埃拉托色尼（Eratosthenes，公元前275一前193）生于希腊在非洲北部的殖民地昔兰尼（cyrene，在今利比亚）。他在昔兰尼和雅典接受了良好的教育，成为了一位博学的哲学家、诗人、天文学家和地理学家。他的兴趣是多方面的，不过他的成就则主要表现在地理学和天文学方面。

－End－