素数筛

素数筛求质数

#include<bits/stdc++.h>
using namespace std;

int n,cnt;
bool ip[1000005];
vector<int> pr;

void xsh(int n)
{
    memset(ip,true,sizeof(ip));
    ip[0] = ip[1] = false;
    for(int i = 2;i <= n;i++)
    {
        if(ip[i])
        {
            pr.push_back(i);
        }
        for(int j = 0;j < pr.size() && pr[j] * i <= n;j++)
        {
            ip[pr[j] * i] = false;
            if(i % pr[j] == 0)
            {
                break;
            }
        }
    }
}

int main()
{
    cin >> n;
    xsh(n);
    for(int i = 2;i <= n;i++)
    {
        if(ip[i])
        {
            cout << i << " ";
            cnt++;
        }
        if(cnt == 5)
        {
            cout << "\n";
            cnt = 0;
        }
    }
    return 0;
}