Contents

1. 1. Description
2. 2. Input
3. 3. Output
4. 4. sample Input
5. 5. sample Output

Description

在数学上，素数的分布没有任何已知规律，因此检测一个数是否素数，只能用比它小的素数来检测整除性质。如果要求出一定范围内的素数表直接检测的代价就太高了。一般采用筛选法的思想：
把从1开始的、某一范围内的正整数从小到大顺序排列，1不是素数，首先把它筛掉。剩下的数中选择最小的数是素数，然后去掉它的倍数。依次类推，直到筛子为空时结束。
如有：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
1不是素数，去掉。剩下的数中2最小，是素数，去掉2的倍数，余下的数是：
3 5 7 9 11 13 15 17 19 21 23 25 27 29
剩下的数中3最小，是素数，去掉3的倍数……如此下去直到所有的数都被筛完，求出的素数为：
2 3 5 7 11 13 17 19 23 29
用筛选的办法求出素数表之后，再进行查询。

求区间m～n之间的素数，其中m,n为整数，且0<=m<=n<=500000。

Input

输入多行，到EOF结束。每行为一个测试用例，两个整数m和n，满足0<=m<=n<=500000。总测试用例数不超过1000个。

Output

输出为m～n之间的所有素数，每个数一行，两个测试用例之间用一个空行分隔。
如果m～n之间没有素数，则输出一个空行。

sample Input

1 2
2 3
8 10
1 11
50 100
900 1000
499900 500000

sample Output

2

2
3

2
3
5
7
11

53
59
61
67
71
73
79
83
89
97

907
911
919
929
937
941
947
953
967
971
977
983
991
997

499903
499927
499943
499957
499969
499973
499979

#include <stdio.h>
int mark[500010];
int i, j;
int main(){

    mark[1] = 1;//1不是素数
    for(i=2;i<=500000;i++)                             //预处理
    {
        if(mark[i]==0)                                 //前面没有因子使mark[i]变成1，说明除了1和本身不能被别的数整除了
        {
            for(j=i+i;j<=500000;j=j+i)                 //整数倍的移动
                mark[j]=1;                             //他的整数倍的数都不是素数，因为因子中除了1和本身还多了他
        }
    }
    int n, m;
    while(scanf("%d %d", &m, &n) != EOF)
    {
        int flag = 0;
        for(i = m; i <= n; i++)
        {
            if(mark[i] == 0)
                {
                    printf("%d\n", i);
                    flag = 1;
                }
        }
        if(flag == 0)
            printf("No!\n");
    }
    return 0;
}