*1179 筛选素数

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

HINT

Append Code

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <stdlib.h>
#include <math.h>
int sushu(int m)
{
    int i;
    int sqrtm=(int)sqrt((double)m);
    if(m==1)
        return 0;
    else if(m==2)
        return 1;
    else if(m%2==0)
        return 0;
    else
    {
       for(i=3;i<=sqrtm;i+=2)
       if((m%i)==0)
       return 0;
    }
    return 1;
}
int a[500005];
int main()
{
    int m,n,i,j,k;
    while(scanf("%d%d",&m,&n)!=EOF)
    {
        k=0;
        memset(a,0,sizeof(a));
        for(i=m;i<=n;i++)
        {
            if(a[i]<0)
                continue;
            if(sushu(i)==1)
            {
                a[i]=1;
                for(j=i+1;j<=n;j++)
                    if(j%i==0)
                    a[j]=-1;
            }
        }
        for(i=m;i<=n;i++)
        {
            if(a[i]==1)
            {
                printf("%d\n",i);
                k++;
            }
        }
        if(k==0)
            printf("\n");
        printf("\n");
    }
    return 0;
}