埃氏筛

埃氏筛求素数

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

int n;
bool ip[100005];

void es(int n)
{
	memset(ip,true,sizeof(ip));
	ip[0] = ip[1] = false;
	for(int i = 2;i * i <= n;i++)
	{
		if(ip[i])
		{
			for(int j = 2 * i;j <= n;j += i)
			{
				ip[j] = false;
			}
		}
	}
	for(int i = 2;i <= n;i++)
	{
		if(ip[i])
		{
			cout << i << " ";
		}
	}
}

int main()
{
    cin >> n;
    es(n);
    return 0;
}