[Solution][Math Theory]SPOJ PRIME1

【题目】

戳这里

【题意】

多次询问给定区间中质数。

【思路】

预处理出以内的质数,每一次筛的时候只用不超过区间右端的质数筛当前区间。可以过。

(话说在这道题上欧拉定理的素数判定方法极其不靠谱。。。)

【代码】

#include<cstdio>
#include<cstring>
#define clear(x , y) memset(x , y , sizeof(x))
const int N = 31622;
bool f[100001];
int pri[20000] , top;
int main()
{
    register int i , j;
    for(i = 2 ; i <= N ; ++i)
    {
        if (!f[i])
            pri[top++] = i;
        for(j = 0 ; j < top ; ++j)
        {
            if (pri[j] * i > N)
                break;
            f[pri[j] * i] = 1;
            if (i % pri[j] == 0)
                break;
        }
    }
    int T;
    scanf("%d" , &T);
    int l , r;
    while(T--)
    {
        scanf("%d%d" , &l , &r);
        clear(f , 1);
        for(i = 0 ; i < top ; ++i)
        {
            if (pri[i] > r)
                break;
            int _min = l % pri[i] == 0 ? l : ((l / pri[i]) + 1) * pri[i];
            if (_min == pri[i])
                _min += pri[i];
            for(j = _min ; j <= r ; j += pri[i])
                f[j - l] = 0;
        }
        for(i = l ; i <= r ; ++i)
        {
            if (f[i - l] && i!= 1)
                printf("%d\n" , i);
        }
        puts("");
    }
    return 0;
}
comments powered by Disqus