【luogu P1865 A % B Problem】 题解

题目链接：https://www.luogu.org/problemnew/show/P1865

其实就是埃拉托色尼筛素数模板...

好像每个数暴力枚举到sqrt()也可以...就算当我无聊练手罢

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn = 1000000 + 10;
bool prime[maxn];
int n, m, left, right, sq, tot = 0;
int main()
{
    memset(prime,0,sizeof(prime));
    scanf("%d%d", &n, &m);
    
    sq = sqrt(m);
    prime[1] = 1;
    for(int i = 2; i <= sq; i++)
        if(prime[i] == 0)
        {
            for(int j = i*i; j <= m; j+=i)
            prime[j] = 1;
        }
    
    for(int i = 1; i <= n; i++)
    {
        scanf("%d%d", &left, &right);
        if(left > m || right > m || left <= 0 || right <= 0) 
        {
            printf("Crossing the line\n");
            continue;
        }
        else
        {
            for(int j = left; j <= right; j++)
            {
                if(prime[j] == 0)
                tot++;
            }    
            printf("%d\n",tot);
            tot = 0;
        }
    
    }
    return 0;
}