https://www.dotcpp.com/oj/problem1084.html?sid=1756019&lang=1#editor

不要小看简单的题目哦。一步步来。

 

 

 

 

 

#include<iostream>
using namespace std;

#define maxn 10000000

bool vis[maxn];
int prime[maxn],x;

void isprime(int n) //埃氏筛
{
    for(int i=2;i<=n;i++)
    {
        if(!vis[i]) prime[x++]=i;
        for(int j=2;j*i<=n;j++)
        {
            vis[i*j]=true;
        }
    }
}


void oulasai(int n)
{
    for(int i=2;i<=n;i++)
    {
        if(!vis[i])prime[x++]=i;//i未被访问过，则i就是素数
        for(int j=0;j<x;j++)
        {
            if(i*prime[j]>n)break;
            vis[i*prime[j]]=true;//prime里的数都比i小，则prime里必有一个（i*prime）的最小质因数                  
             if(i%prime[j]==0)break;//如果i%prime==0则prime是（i*prime）最小质因数，
             //然后（i*prime）只会在这里被筛选过一次，
             //比（i*prime）大的有最小质因数prime的数会在（i+n）时轮到该prime，然后筛掉 
         } 
    }
}

void isprime2(int n)
{
    for(int i=0;i<=n;i++)
    {
        prime[i]=1;
    }
    for(int i=2;i<=n/2;i++)
    {
        for(int j=2;j*i<=n;j++)
        {
            prime[j*i]=0;
        }
    }
}
//好像是假的 
void oulasai2(int n)
{
    for(int i=0;i<=n;i++)
    {
        prime[i]=1;
    }
    for(int i=2;i<=n;i++)
    {
        for(int j=2;i*j<=n;j++)
        {
            if(prime[j*i]==0)continue;
            prime[j*i]=0;
        }
    }
}

int main()
{
    int n;
    cin>>n;
    
    isprime2(n);
    prime[0]=0;
    prime[1]=0;
    for(int i=0;i<=n;i++)
    {
        if(prime[i]!=0)cout<<i<<endl;
    }
    return 0;
}