素?cái)?shù)篩選
一般線性篩法：
給定一個范圍，先假定這些數(shù)全是素?cái)?shù)，然后從2開始，如果一個數(shù)i是素?cái)?shù)，那么這個素?cái)?shù)乘以大于等于i的數(shù)肯定不是素?cái)?shù)。

#include<cstdio>
#include<cstring>
#define maxn 8010
bool isPrime[maxn];
int primes[maxn];
int cnt;
void make_prime()
{
    cnt=0;
    for(int i=0;i<maxn;i++)
    {
        isPrime[i]=true;
    }
    isPrime[0]=false;
    isPrime[1]=false;
    for(int i=2;i<maxn;i++)
    {
        if(isPrime[i])
        {
            primes[cnt++]=i;
            for(int j=i*i;j<maxn;j+=i)//以i*i起步比i*2起步要快
            {
                isPrime[j]=false;
            }
        }
    }
    return;
}
int main()
{
    make_prime();
    for(int i=0;i<cnt;i++)
    {
        printf("%d\n",primes[i]);
    }
    return 0;
}

快速線性篩法:
如果一個數(shù)num是合數(shù)，那么這個數(shù)可以表示為num=p1*p2*...*pn,其中，p1,p2,..pn是素?cái)?shù)；p1<p2<...<pn;
不重復(fù)的篩法：
給定一個范圍，先假定所有數(shù)是素?cái)?shù)，從2開始。
如果i是素?cái)?shù)，那么不大于i的素?cái)?shù)乘以i得到的合數(shù)一定不會重復(fù)
如果i是合數(shù)，假設(shè)i=p1*p2*...*pn，p1是最小的素?cái)?shù)，那么不大于p1的素?cái)?shù)乘以i得到的合數(shù)不會重復(fù)

#include<cstdio>
#include<string.h>
using namespace std;
const int MAXN=10000;
int isPrime[MAXN];
int primes[MAXN];
int cnt;
void make_prime()
{
    memset(isPrime,1,sizeof(isPrime));
    isPrime[0]=0;
    isPrime[1]=0;
    cnt=0;
    for(int i=2;i<MAXN;i++)
    {
        if(isPrime[i])
        {
            primes[cnt++]=i;
        }
        for(int j=0;j<cnt&&i*primes[j]<MAXN;j++)
        {
            isPrime[i*primes[j]]=0;
            if(!(i%primes[j])) break;
        }
    }

}
int main()
{
    make_prime();
    for(int i=0;i<cnt;i++)
    {
        printf("%d\n",primes[i]);
    }
}

scut oj 1035

#include<stdio.h>
#include <string.h>
using namespace std;
const int MAXN = 2147483;
bool com[MAXN];//判斷是否和數(shù)
int primes, prime[MAXN/10];
void prime_maker(int n)
{
    primes = 0;
    memset(com,false,sizeof(com));
    com[0] = com[1] = true;
    for (int i = 2; i <= n; ++i)
    {
        if (!com[i])
        {
            prime[++primes] = i;
        }
        for (int j = 1; j <= primes && i*prime[j] <= n; ++j)
        {
            com[i*prime[j]] = true;
            if (!(i % prime[j]))
                break;
        }
    }
}
int main()
{
    int n;
    scanf("%d",&n);
    prime_maker(n);
    for(int i=1;i<=primes;i++)
    {
        printf("%d ",prime[i]);
    }
    printf("\n");
}