素数是指除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－
,
