筛法求n以内的素数

筛法求素数：把2到n中所有的数都列出来，然后从2开始，先划掉n内所有2 的倍数，然后每次从下一个剩下的数(必然是素数)开始，划掉其n内的所有倍数。最后剩下的数，就都是素数。

空间换时间，加快了计算速度。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define maxn 1000000
using namespace std;
bool isPrime[maxn+10];//判断是否为素数的数组
int main()
{
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    for(int i=2;i<=n;i++)//开始假设每个数都是素数
        isPrime[i]=true;
    for(int i=2;i<=n;i++)
    {
        if(isPrime[i])//只标记素数的倍数
        {
            for(int j=2*i;j<=n;j+=i)//将素数的倍数标记为非素数
                isPrime[j]=false;
        }
    }
    for(int i=2;i<=n;i++)
        if(isPrime[i])
            cout<<i<<endl;
    return 0;
}