Codeforces Noldbach problem
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<bitset>
#define sf scanf
#define pf printf
#define mx 1010
using namespace std;
bitset<mx>bs;
int prm[mx], plen=0;
void sieve()
{
int i,j;
bs.set();
bs[0]=bs[1]=0;
for(i=2; i<mx; i++)
{
if(bs[i])
{
prm[plen++] = i;
for(j=i*i; j<mx; j+=i)
{
bs[j] = 0;
}
}
}
//for(i=0; i<100; i++) pf("%d ",prm[i]);
}
bool isPrime(int n)
{
if(n < mx) return bs[n];
for(int i=0; i<plen and prm[i] * prm[i] <= n; i++)
{
if(!(n % prm[i])) return false;
}
return true;
}
int noldbach[mx];
void precalculate()
{
int i,j;
for(i=2; i<mx; i++)
{
for(j=0; prm[j] < i; j++)
{
if( isPrime( (prm[j] + prm[j-1] + 1) ) and (prm[j] + prm[j-1] + 1) <= i)
{
//cout << prm[j] + prm[j-1] + 1 << "\n";
noldbach[i]++;
}
}
}
}
int main()
{
sieve();
precalculate();
int n,k;
while(~sf("%d %d", &n, &k))
{
//pf("%d\n", noldbach[n]);
if(noldbach[n] >= k)
{
pf("YES\n");
}
else
{
pf("NO\n");
}
}
return 0;
}
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<bitset>
#define sf scanf
#define pf printf
#define mx 1010
using namespace std;
bitset<mx>bs;
int prm[mx], plen=0;
void sieve()
{
int i,j;
bs.set();
bs[0]=bs[1]=0;
for(i=2; i<mx; i++)
{
if(bs[i])
{
prm[plen++] = i;
for(j=i*i; j<mx; j+=i)
{
bs[j] = 0;
}
}
}
//for(i=0; i<100; i++) pf("%d ",prm[i]);
}
bool isPrime(int n)
{
if(n < mx) return bs[n];
for(int i=0; i<plen and prm[i] * prm[i] <= n; i++)
{
if(!(n % prm[i])) return false;
}
return true;
}
int noldbach[mx];
void precalculate()
{
int i,j;
for(i=2; i<mx; i++)
{
for(j=0; prm[j] < i; j++)
{
if( isPrime( (prm[j] + prm[j-1] + 1) ) and (prm[j] + prm[j-1] + 1) <= i)
{
//cout << prm[j] + prm[j-1] + 1 << "\n";
noldbach[i]++;
}
}
}
}
int main()
{
sieve();
precalculate();
int n,k;
while(~sf("%d %d", &n, &k))
{
//pf("%d\n", noldbach[n]);
if(noldbach[n] >= k)
{
pf("YES\n");
}
else
{
pf("NO\n");
}
}
return 0;
}
Comments
Post a Comment