#埃氏筛法
埃拉托斯特尼筛法（希腊语：κόσκινον Ἐρατοσθένους，英语：sieve of Eratosthenes ），简称埃氏筛，也称素数筛。这是一种简单且历史悠久的筛法，用来找出一定范围内所有的质数。

所使用的原理是从2开始，将每个质数的各个倍数，标记成合数。一个质数的各个倍数，是一个差为此质数本身的等差数列。此为这个筛法和试除法不同的关键之处，后者是以质数来测试每个待测数能否被整除。

埃拉托斯特尼筛法是列出所有小质数最有效的方法之一，其名字来自于古希腊数学家埃拉托斯特尼，并且被描述在另一位古希腊数学家尼科马库斯所著的《算术入门》中

例题

51Nod - 1181
https://cn.vjudge.net/contest/202817#problem/J

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<iostream>
using namespace std;

typedef long long LL;
const int maxn = 1500000;
int prime[maxn + maxn],tmp[maxn],a[maxn + 10];

void init()
{
    int cnt = 1;
    a[1] = 0, a[2] = 1;
    for(LL i = 3; i <= maxn; i++)
    {
        if(i % 2 ) a[i] = 1;
        else a[i] = 0;
    }
    for(int i = 3; i <= sqrt(maxn); i++)
    {
        if(a[i])
        {
            for(LL j = i * 2; j <= maxn; j += i)
                a[j] = 0;
        }
    }
    LL num = 1;
    for(LL i = 1; i <= maxn; i++)
        if(a[i]) tmp[num++] = i;
    memset(prime,0,sizeof(prime));
    for(LL i = 1; i < num; i++)
        if(a[i]) prime[tmp[i]] = 1;
}

int main()
{
    int n;
    init();
    while(scanf("%d",&n) == 1)
    {
        for(LL i = n; ; i++)
            if(prime[i])
            {
                printf("%lld\n",i);
                break;
            }
    }
    return 0;
}