相关文章推荐
热心肠的香蕉  ·  git ...·  7 月前    · 
内向的火柴  ·  臺灣醫學會·  7 月前    · 
忐忑的薯片  ·  Differences behaviour ...·  8 月前    · 

题目:算法-哥德巴赫猜想-

问题描述(原题是英文,这里是翻译过后的版本):
对于任意n大于或等于4的偶数,至少存在一对质数p1和p2,使n = p1 + p2。这个猜想至今没有被证实,也没有被否定。没人能确定这个猜想是否成立。然而,如果有的话,为一个给定的偶数,人们可以找到这样一对素数。这里的问题是,编写一个程序,对于给定的偶数,报告满足猜想条件的所有质数对的数目。
一个偶数序列作为输入。对应于每个数字,程序应该输出上述对的数量。注意,我们感兴趣的是本质上不同的对的数量,因此你不应该把(p1, p2)和(p2, p1)分别算作两对不同的对。

输入:
每个输入行都有一个整数。你可以假设每个整数都是偶数,大于或等于4小于2^15。输入的末尾用数字0表示。
输出:
每个输出行应该包含一个整数。输出中不应该出现其他字符。
样例输入:
4
10
16
0
样例输出:
1
2
2

1. 问题分析

1.1 算法核心

验证哥德巴赫猜想是经典的数学算法题,也就是数学问题用计算机来解决,因而算法核心就是数学模拟问题;

1.2 算法分析

因为我们要找素数对,所以得先有一个素数表嘛,第一步先写一个标准埃氏筛选法获得素数表,这里素数表可以取的大一点,因为系统输入的这个整数不超过2 15 ,所以我们的素数表可以取大一点。
有了素数表以后就可以数学模拟了,要找到一对素数满足素数对和等于某个整数,那肯定是一大一小,或者两个差不多大的素数,根据题目得知(p2,p1)和(p1,p2)这两对素数只算一组不同的素数对;
诶,这个时候我突然想到了算法中常用的小技巧-two pointers,定义两个指针,一个从素数表首开始,一个从素数表尾开始,这样不仅可以优化时间复杂度,也可以避免素数对的重复计数,于是就先根据输入的整数(以下简称为t)找到距离t最近的那个素数,然后让一个指针指向这个位置,然后另一个指针从素数表首开始,
就是把素数表想象成一个线性序列,
第一个指针指向首个元素,
第二个指针指向距离t最大的素数,
然后开始计算素数对的和,
若等于t,那么素数对计数器加一,之后第一个指针向右移动一位第二个指针向左移动一位,
若小于t说明不够大,那第一个指针向右移动一位,
若大于t说明不够小,那第二个指针向左移动一位,
这样不断匹配,直到第一个指针和第二个指针指向同一个元素,或者第一个指针指向的元素大于第二个指针指向的元素,此时终止循环,根据题目要求输出计数器的值即可;

2. 解决方案

#include <iostream>
using namespace std;
#define maxLength 40010
int n, primeTable[maxLength], primeCounts = 0, t;
bool primeSign[maxLength] = { 0 };
void findPrimeTable();
int GoldbachConjecture(int max);
int main()
	findPrimeTable();
	while (scanf("%d", &t) != EOF && t != 0)
		t = GoldbachConjecture(t);
		printf("%d\n", t);
	return 0;
void findPrimeTable()
	for (int i = 2; i < maxLength; i++)
		if (primeSign[i] == false)
			primeTable[primeCounts++] = i;
			for (int j = i + i; j < maxLength; j += i)
				primeSign[j] = true;
int GoldbachConjecture(int max)
	int counts = 0, tmp, overlapSign = 1;
	int *left, *right;
	left = primeTable;
	for(int i = 2; i < maxLength; i++)
		if(primeTable[i] > max)
			right = &primeTable[i - 1];
			break;
	while(*left <= *right && *right >= 2)
		tmp = *left + *right;
		if(tmp == max)
			counts++;
			left++, right--;
		else if(tmp < max)
			left++;
			right--;
	return counts;

3. 资源分享

旗木白哉のGitHub:
https://github.com/YangMengHeng
C++ / C源代码下载地址:
https://github.com/YangMengHeng/myCode/tree/master/VSCode
Java源代码下载地址:
https://github.com/YangMengHeng/myCode/tree/master/Java
旗木白哉のblog源代码下载地址:
https://github.com/YangMengHeng/myCode/tree/master/%E6%97%97%E6%9C%A8%E7%99%BD%E5%93%89%E3%81%AEblog

算法-哥德巴赫猜想问题概述1. 问题分析1.1 算法核心1.2 算法分析2. 解决方案3. 资源分享问题概述题目:算法-哥德巴赫猜想-问题描述(原题是英文,这里是翻译过后的版本):对于任意n大于或等于4的偶数,至少存在一对质数p1和p2,使n = p1 + p2。这个猜想至今没有被证实,也没有被否定。没人能确定这个猜想是否成立。然而,如果有的话,为一个给定的偶数,人们可以找到这样一对素数。这里的问题是,编写一个程序,对于给定的偶数,报告满足猜想条件的所有质数对的数目。一个偶数序列作为输入。对应 那么,接下来,我们就来研究研究巴赫猜想的验证及优化方案: 第一步,先建立头文件 “mec.h”(建立头文件的目的:简化程序,使程序更加直观,编写更加方便,在查找错误以及修改程序时,更加方便): #ifndef _MEC_H_ #define _MEC_H_ typedef unsigned char boo...
Algorithm JAVA写算法 验证巴赫猜想巴赫猜想换成现代陈述为:任何一个大于5的整数都可以写成3个质数之和;另一个版本(欧拉):任何一个大于2的偶数都可以写成2个质数之和。 现在所说的巴赫猜想一般都是置第二种,两个多世纪过去了,这一猜想即无法被证实也没有被推翻。 现在用java写算法,通过程序在4~100内验证这个猜想。 先获取4-100内所有偶数:package algo
数学领域著名的“巴赫猜想”的大致意思是:任何一个大于2的偶数总能表示为两个素数之和。比如:24=5+19,其中5和19都是素数。本实验的任务是设计一个程序,验证20亿以内的偶数都可以分解成两个素数之和。 输入格式: 输入在一行中给出一个(2, 2 000 000 000]范围内的偶数N。 输出格式: 在一行中按照格式“N = p + q”输出N的素数分解,其中p ≤ q均为素数。又因为...
下有模板题: Description 验证巴赫猜想:任何一个大于6的偶数均可表示为两个素数之和。例如6=3+3, 8=3+5,…18=5+13(若某一偶数可分成多组素数和,只取前一个加数最小的那一个组合)。要求将6-99之间的偶数都表示成两个素数之和,输出时每行输出5组。 Input Output 输出格式:每个整数占两位,且左对齐,两个式子间空格隔开。 Sample Input Sample Output 6 =3 +3 8 = 把坚持数字是否在数组中,变成直接查找读取,速度快到不敢想象,代价依然是空间。 升级的代码 def Test2(maxLimit, primeList, lenth, rawList): for i in rang... 这个代码将偶数 `n` 分解成两个质数的和。如果 `n` 是奇数或小于等于2,则返回 `None`。如果无法找到两个质数的和等于 `n`,则也返回 `None`。 ### 回答2: 巴赫猜想是一个数论问题,它的基本观点是每个大于2的偶数都可以表示为两个质数之和。为了验证巴赫猜想,我们可以使用Python编写一个程序来遍历所有大于2的偶数,然后检查它们是否可以表示为两个质数之和。 首先,我们可以创建一个函数来判断一个数是否为质数。质数是只能被1和自身整除的大于1的整数。我们可以使用循环来检查该数是否可以被其他数字整除,如果能被整除,则说明它不是质数。 接下来,我们可以创建一个循环来遍历所有大于2的偶数。对于每个偶数,我们可以再次使用一个循环来寻找两个质数的组合,使它们的和等于当前的偶数。我们可以使用嵌套循环来遍历所有可能的质数组合,并检查它们的和是否等于当前的偶数。 如果我们找到了一个质数组合,使它们的和等于当前偶数,那么可以打印出这个组合并继续进行下一个偶数的验证。如果没有找到这样的组合,那么说明当前偶数不能被巴赫猜想所验证。 最后,我们可以在主程序中调用这个函数来完成所有大于2的偶数的验证。我们可以定义一个范围,例如从4到300的所有偶数,并将它们传递给我们的函数进行验证。在循环中,我们可以打印出每个偶数是否通过了验证。 通过这样的程序,我们可以在Python中验证巴赫猜想,并找到所有满足猜想的偶数。当然,由于算法的复杂性,我们可能需要更多的计算时间来验证更大的偶数。 ### 回答3: 巴赫猜想是一个数论的猜想,它声称每个大于2的偶数可以表示为两个素数之和。我们可以使用Python来验证巴赫猜想。 首先,我们需要编写一个函数来检查一个给定的数字是否为素数。这个函数可以使用循环从2到这个数字的平方根来检查是否有因数,如果有则返回False,否则返回True。 接下来,我们可以编写另一个函数来验证巴赫猜想。这个函数将接受一个偶数作为参数,并遍历从2到这个偶数的一半的所有数字。对于每个数字i,我们将调用素数检查函数来检查i和(偶数-i)是否都是素数。如果是,则返回True,否则继续遍历。 最后,我们可以编写一个主函数来测试我们的验证函数。我们可以使用一个循环来生成一系列偶数,并调用验证函数来检查它们是否满足巴赫猜想。如果验证函数返回False,则打印出不能满足猜想的数字。 在运行程序后,我们可以看到所有小于300的偶数都满足巴赫猜想。 以下是示例代码: ```python import math def is_prime(n): if n < 2: return False for i in range(2, math.isqrt(n) + 1): if n % i == 0: return False return True def verify_goldbach_conjecture(num): for i in range(2, num // 2 + 1): if is_prime(i) and is_prime(num - i): return True return False def main(): for num in range(4, 301, 2): if not verify_goldbach_conjecture(num): print(num, "不能满足巴赫猜想。") main() 这段代码会打印出不能满足巴赫猜想的偶数,但是在运行过程中,你将会注意到没有任何数字被打印出来,这说明所有小于300的偶数都满足巴赫猜想