素数筛选

素数筛选
一般线性筛法：
给定一个范围，先假定这些数全是素数，然后从2开始，如果一个数i是素数，那么这个素数乘以大于等于i的数肯定不是素数。

#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;
}

快速线性筛法:
如果一个数num是合数，那么这个数可以表示为num=p1*p2*...*pn,其中，p1,p2,..pn是素数；p1<p2<...<pn;
不重复的筛法：
给定一个范围，先假定所有数是素数，从2开始。
如果i是素数，那么不大于i的素数乘以i得到的合数一定不会重复
如果i是合数，假设i=p1*p2*...*pn，p1是最小的素数，那么不大于p1的素数乘以i得到的合数不会重复

#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];//判断是否和数
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");
}