HDU1397 POJ2909 UVA686 UVALive5674 ZOJ1657 Goldbach's Conjecture(II)

Regionals 1998 >> Asia - Tokyo

问题链接：HDU1397 POJ2909 UVA686 UVALive5674 ZOJ1657 Goldbach's Conjecture(II)。

问题简述：参见上述链接。

问题分析：

这个问题是验证哥德巴赫猜想，对于输入的n，计算和等于n的奇素数对的个数。

不预先打表时间上会超时。

程序说明：

这个问题，HDU1397和UVA686的测试数据是不一样的。最初做的程序，HDU中AC，而UVA中WA。估计原因是UVA868中的n是包含奇数的，例如７＝２＋５。所以后来写的程序将计算素数对的循环做了修改，程序通过了。

这里分别给出C语言程序和C++语言程序的两个版本。

AC的C语言程序如下：

/* HDU1397 POJ2909 UVA686 Goldbach's Conjecture(II) */
#include <stdio.h>
#include <math.h>
#define MAXN 32767
int prime[MAXN+2] = {0, 0, 1, 1, 0};
// 试除法判断一个数是否为素数
int isprime(int n)
{
int end2, i;
end2 = sqrt(n);
for(i=3; i<=end2; i+=2) {
if(n % i == 0)
break;
}
return i > end2 ? 1 : 0;
}
void maketable(int n)
{
int i;
for(i=5; i<n; i+=2) {
prime[i] = isprime(i);
prime[i+1] = 0;
}
}
int main(void)
{
int n;
int count, i;
// 打表
maketable(MAXN);
while(scanf("%d", &n) != EOF) {
// 判定结束条件
if(n == 0)
break;
// 计算素数对个数
count = 0;
for(i=2; i<=n/2; i++)
if(prime[i] && prime[n-i])
count++;
// 输出结果
printf("%dn", count);
}
return 0;
}

AC的C++语言程序如下：

/* HDU1397 POJ2909 UVA686 UVALive5674 Goldbach's Conjecture(II) */
#include <iostream>
#include <cmath>
#include <cstdio>
using namespace std;
const int MAXN = 2000000;
bool prime[MAXN+1] = {false, false, true};
// 埃氏筛选法
void esieve(bool sflag[], int n)
{
// 初始化
for(int i=3; i<=n; i++) {
sflag[i++] = true;
sflag[i] = false;
}
// 筛选
int max = sqrt(n);
for(int i=3; i<=max; i++) {
if(sflag[i]) {
for(int j=i+i; j <= n; j+=i)
sflag[j] = false;
}
}
}
int main()
{
esieve(prime, MAXN);
int n, count, i;
while(scanf("%d", &n) != EOF) {
// 判定结束条件
if(n == 0)
break;
// 计算素数对个数
count = 0;
for(i=2; i<=n/2; i++)
if(prime[i] && prime[n-i])
count++;
// 输出结果
printf("%dn", count);
}
return 0;
}

HDU中AC，而UVA中WA的C语言程序如下：

/* HDU1397 POJ2909 UVA686 Goldbach's Conjecture(II) */
#include <stdio.h>
#include <math.h>
#define MAXN 32767
int prime[MAXN+2] = {0, 0, 1, 3, 0};
// 试除法判断一个数是否为素数
int isprime(int n)
{
int end2, i;
end2 = sqrt(n);
for(i=3; i<=end2; i+=2) {
if(n % i == 0)
break;
}
return i > end2 ? 1 : 0;
}
void maketable(int n)
{
int i;
for(i=5; i<n; i+=2) {
prime[i] = isprime(i);
prime[i+1] = 0;
}
}
int main(void)
{
int n;
int count, i;
// 打表
maketable(MAXN);
while(scanf("%d", &n) != EOF) {
// 判定结束条件
if(n == 0)
break;
// 计算素数对个数
count = 0;
for(i=3; i<=n/2; i+=2)
if(prime[i] && prime[n-i])
count++;
// 输出结果
printf("%dn", count);
}
return 0;
}