【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 =  + ;

 bool prime[maxn];

 int n, m, left, right, sq, tot = ;

 int main()

 {

     memset(prime,,sizeof(prime));

     scanf("%d%d", &n, &m);

     sq = sqrt(m);

     prime[] = ;

     for(int i = ; i <= sq; i++)

         if(prime[i] == )

         {

             for(int j = i*i; j <= m; j+=i)

             prime[j] = ;

         }

     for(int i = ; i <= n; i++)

     {

         scanf("%d%d", &left, &right);

         if(left > m || right > m || left <=  || right <= )

         {

             printf("Crossing the line\n");

             continue;

         }

         else

         {

             for(int j = left; j <= right; j++)

             {

                 if(prime[j] == )

                 tot++;

             }

             printf("%d\n",tot);

             tot = ;

         }

     }

     return ;

 }