UVa 543 - Goldbach's Conjecture

  题目大意:给一个偶数,判断是否是两个素数的和。

  先用sieve方法生成一个素数表,然后再进行判断即可。

 #include <cstdio>
#include <vector>
#include <bitset>
using namespace std;
typedef vector<int> vi;
typedef long long ll;
#define MAXN 1000000 vi primes;
bitset<MAXN+> bs; void sieve(ll upper)
{
bs.set();
bs.set(, false);
bs.set(, false);
for (ll i = ; i <= upper; i++)
if (bs.test((size_t)i))
{
for (ll j = i*i; j <= upper; j += i)
bs.set((size_t)j, false);
primes.push_back((int)i);
}
} int main()
{
#ifdef LOCAL
freopen("in", "r", stdin);
#endif
sieve(MAXN);
int n;
while (scanf("%d", &n) && n)
{
int idx = ;
bool ok = false;
while (primes[idx] * <= n)
{
int t = n - primes[idx];
if (bs.test((size_t)t))
{
ok = true;
break;
}
idx++;
}
if (ok) printf("%d = %d + %d\n", n, primes[idx], n-primes[idx]);
else printf("Goldbach's conjecture is wrong.\n");
}
return ;
}
上一篇:a note of R software write Function


下一篇:phython编写图形界面