C-良心の出題者がまた来た!Gym - 241030C
タイトル
この問題は主に:1素ふるい2フェルマ二乗の定理
この問題は主に: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;
}