洛谷 P1304:哥德巴赫猜想 ← Python 实现

【题目来源】
https://www.luogu.com.cn/problem/P1304

【题目描述】
输入一个偶数 N,验证 4∼N 所有偶数是否符合哥德巴赫猜想:任一大于 2 的偶数都可写成两个质数之和。如果一个数不止一种分法,则输出第一个加数相比其他分法最小的方案。
例如 10,10=3+7=5+5,则 10=5+5 是错误答案。

【输入格式】
第一行输入一个正偶数 N。

【输出格式】
输出 (N−2)/2 行。对于第 i 行:
首先先输出正偶数 2i+2,然后输出等号,再输出加和为 2i+2 且第一个加数最小的两个质数,以加号隔开。

【输入样例】
10

【输出样例】
4=2+2
6=3+3
8=3+5
10=3+7

【说明/提示】
数据保证,4≤N≤10000。

【算法分析】
● 本题进行输出时要用 print(f"{i}={j}+{i-j}"),而不能用 print(i,"=",j,"+",i-j)。
这是由输出格式决定的。例如,用 print(i,"=",j,"+",i-j) 进行输出 8=3+5 时,会变成 8 = 3 + 5。即中间多了不少空格,被系统判错。

●关于素数的常见问题题解,详见:
https://blog.csdn.net/hnjzsyjyj/article/details/127699346
https://blog.csdn.net/hnjzsyjyj/article/details/144323880
https://blog.csdn.net/hnjzsyjyj/article/details/144152999
https://blog.csdn.net/hnjzsyjyj/article/details/119729401

【算法代码】

def isPrime(n):
    if n<2:return False
    for i in range(2,n):
        if n%i==0:return False
    return True

n=eval(input())
for i in range(4,n+1,2):
    for j in range(2,i):
        if isPrime(j) and isPrime(i-j):
            print(f"{i}={j}+{i-j}")
            break

【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/130044998
https://blog.csdn.net/hnjzsyjyj/article/details/119729401
https://blog.csdn.net/hnjzsyjyj/article/details/127699346
https://www.luogu.com.cn/problem/solution/P1304

 

作者:hnjzsyjyj

物联沃分享整理
物联沃-IOTWORD物联网 » 洛谷 P1304:哥德巴赫猜想 ← Python 实现

发表回复