素数筛选

1、取余数方法

#include<stdio.h>
#define N 100
int main()
{
    int prime[N];
    int i,j;
    for(i=1;i<=N;i++)
        prime[i]=1;
    prime[0]=prime[1]=0;
    for(i=2;i*i<=N;i++)//提供基数
        {
            if(prime[i]==1)
            {
                for(j=2*i;j<=N;j++)//除以几倍
                    {
                        if(prime[j]==0)
                            continue;
                        if(j%i==0)
                            prime[j]=0;
                    }
            }
        }
            

}

2、加法

#define SZ 10000
int prime[SZ];
void init()
{
    int i, j;
    for (i = 0; i < SZ; i++)
    {
        prime[i] = 1;
    }
    prime[0] = prime[1] = 0;
    for (i = 2; i < SZ; i++)
    {
        if (prime[i])
        {
            for (j = i + i; j < SZ; j += i)//每次递增自己，就是相当于倍数递增
                prime[j] = 0;
        }
    }
}