这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。
大家都说是水题,可能是自己实力差把,我感觉可不水。
我用普通的判断sqrt(n)的方法求素数,结果TLE了。
看了论坛一个朋友的方法,是用的筛选法。
#include
#include
#include
using namespace std;
/*
bool Is_odd_prime(int n)
{
int i;
if(n % 2 == 0)
return 0;
for(i = 2; i < sqrt(double(n)); i++)
if(n % i == 0)
return 0;
if(i == n/2)
return 1;
}
*/
int prime[1000000];
int main()
{
int i, j;
memset(prime, 1, sizeof(prime));
for(i = 2; i < 1000; i++)
if(prime[i])
for(j = i*2; j < 1000000; j+=i)
prime[j] = 0;
int n;
while(scanf("%d", &n;) && n != 0)
{
int i;
for(i = 2; i <= n/2; i++)
if(prime[i] && prime[n-i])
{
printf("%d = %d + %d\n", n, i, n-i);
break;
}
if(i == n/2+1)
printf("Goldbach's conjecture is wrong.\n");
}
return 0;
}