C-良心の出題者がまた来た!Gym - 241030C

6372 ワード

タイトル
この問題は主に:1素ふるい2フェルマ二乗の定理 :2以外の素数は2種類に分けることができる:1種類はa^2 + b^2という形式の素数集合と、もう1種類はこの形の素数集合として表すことができない.一方、``a 2+b 2と表すことができるmodの結果は1である.
#include 
#include
using namespace std;
const long maxn = 3e7+5;
bool prime[maxn];
bool y[maxn];
void Seve_Prime()
{
    memset(prime, true, sizeof(prime));
    prime[0] =prime[1] = false;

    for(long i = 2; i*i < maxn; i++)
    {

        if(prime[i] == true)
        {

            for(long j = i*2; j <= maxn; j+=i)
            {
                prime[j] = false;
            }
        }
    }


}





int main()
{
    long l, r;
    scanf("%ld %ld", &l, &r);
    Seve_Prime();

    long cnt = 0;


    for(long i = l; i <= r; i++)
    {
        if(i%4 == 1&& prime[i])cnt++;

    }
    cout<<cnt<<endl;


    return 0;
}