// 第一种方法
#include <stdio.h>
int n=10000;
int prime[3000];
int total=0;
int isprime(int k)
{
for(int i=0;i<total;i++)
if(k%prime[i]==0)
return 0;
return 1;
}
int main()
{
for(int i=2;i<n;i++)
if(isprime(i))
prime[total++]=i;
return 0;
}
时间复杂度相对于
时间复杂度高
// 第二种方法 筛选法
#include <stdio.h>
#include<string.h>
#include <math.h>
#define N 1e6
int isprime[1000000];
int SQRT=ceil(sqrt((double)N)); //返回大于或者等于指定表达式的最小整数
int prime()
{
memset(isprime,1,sizeof(isprime));
int i;
isprime[0]=isprime[1]=0;
for(i=0;i<=SQRT;i++)
{
if(isprime[i])
for(int j=i*i;j<=N;j+=i)
isprime[j]=0;
}
}
尽量使用第二种方法；
如果程序需要打素数表，则将第二个程序改为：
const int N=10000;
int primes[N+1];
const int SQRT=ceil(sqrt((double)N));
void esieve()
{
memset(primes,1,sizeof(primes));
primes[0]=primes[1]=0;
for(int i=0;i<=SQRT;i++)
{
if(primes[i])
{
for(int j=i*i;j<N;j+=i)
primes[j]=0;
}
}
for(int i=2,j=0;i<=N;i++)
if(primes[i])
primes[j++]=i;
}
const int maxn=50001;
int prime[maxn],cnt=0;
bool isprime[maxn];
void doprime()
{
memset(isprime,1,sizeof(isprime));
isprime[0]=isprime[1]=0;
for(ll i=2;i<maxn;i++)
{
if(isprime[i])
{
prime[cnt++]=i;
for(ll j=i*i;j<maxn;j+=i)
isprime[j]=0;
}
}
}
参考链接
第三种 高效筛法 （速度比 Eratosthenes筛选法 快 两到四倍）
const int maxn=1e8;
bool flag[maxn];
int prime[maxn/3],pi;
void getprime2()
{
pi=0;
memset(flag,0,sizeof(flag));
for(int i=2;i<maxn;i++)
{
if(!flag[i])
prime[pi++]=i;
for(int j=0;(j<pi)&&(i*prime[j]<maxn);j++)
{
flag[i*prime[j]]=true;
if(i%prime[j]==0)
break;
}
}
}
