工学1号馆

home

« | 返回首页 | »

Project Euler 46–Goldbach’s other conjecture

By Wu Yudong on August 20, 2018

Goldbach’s other conjecture

It was proposed by Christian Goldbach that every odd composite number can be written as the sum of a prime and twice a square.

9 = 7 + 2×12
15 = 7 + 2×22
21 = 3 + 2×32
25 = 7 + 2×32
27 = 19 + 2×22
33 = 31 + 2×12

It turns out that the conjecture was false.

What is the smallest odd composite that cannot be written as the sum of a prime and twice a square?


哥德巴赫的另一个猜想

克里斯蒂安·哥德巴赫曾经猜想,每个奇合数可以写成一个素数和一个平方的两倍之和。

9 = 7 + 2×12
15 = 7 + 2×22
21 = 3 + 2×32
25 = 7 + 2×32
27 = 19 + 2×22
33 = 31 + 2×12

最终这个猜想被推翻了。

最小的不能写成一个素数和一个平方的两倍之和的奇合数是多少?

//(Problem 46)Goldbach's other conjecture
// Completed on Fri, 26 Jul 2013, 16:58
// Language: C11
//
// 版权所有(C)wu yudong
// 博客地址:http://www.wuyudong.com
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<ctype.h>
#include<stdlib.h>
#include<stdbool.h>

bool issquare(int n)  //判断一个自然数是否为一个平方数
{
	if (ceil(sqrt(n)) * ceil(sqrt(n)) == n)
		return true;
	else
		return false;
}

bool isprim(int n)				//素数判断
{
	for (int i = 2; i * i <= n; i++) {
		if (n % i == 0)
			return false;
	}
	return true;
}

bool judge(long long n)
{
	int i = 1;
	long long t;
	while ((t = (n - 2 * (i * i))) > 0) {
		if (isprim(t))
			return true;
		i++;
	}
	return false;
}

int main()
{
	for (long long i = 1001; i < 100000000; i = i + 2) {
		if (!isprim(i) && !judge(i)) {
			printf("%lld\n", i);
			break;
		}
	}
	return 0;
}

Answer:5777

Completed on Fri, 26 Jul 2013, 23:58

如果文章对您有帮助,欢迎点击下方按钮打赏作者

Comments

No comments yet.
To verify that you are human, please fill in "七"(required)