算法

朴素筛法求素数

int primes[N], cnt;     // primes[]存储所有素数
bool st[N];         // st[x]存储x是否被筛掉

void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (st[i]) continue;
        primes[cnt ++ ] = i;
        for (int j = i + i; j <= n; j += i)
            st[j] = true;
    }
}

C++ 代码

#include<cstdio>
using namespace std;

const int sz=1e6+1;
int n,i,j,a[sz],b[sz],ct;

int main()
{
    scanf("%d",&n);

    for(i=2;i<=n;++i)
    if(!a[i])
    {
        b[++ct]=i;
        for(j=i<<1;j<=n;j+=i)a[j]=1;
    }

    printf("%d",ct);

    return 0;
}