前言:
现时兄弟们对“python求素数函数”都比较重视,兄弟们都需要了解一些“python求素数函数”的相关知识。那么小编同时在网摘上网罗了一些对于“python求素数函数””的相关内容,希望各位老铁们能喜欢,同学们一起来了解一下吧!原题解答
本次的题目如下所示:
哥德巴赫猜想的内容如下:任何大于2的偶数,都可以表示成两个素数的和。
为了验证哥德巴赫猜想的正确性,请编写一个程序,输入一个大于2的偶数,输出两个素数的和。
输入:
一个大于2的偶数
输出:
两个素数 (两个数的和为输入的数)
输入样例:
10
输出样例:
3 7
这是一个经典的数学问题,我们首先要解决的问题是:如何判断一个数是素数。之前我们曾经讲过使用Python判断素数,我们可以把判断一个数是否为素数写成函数。
from math import sqrtdef is_prime(n): flag = True for i in range(2, int(sqrt(n)) + 1): if n % i == 0: flag = False break return flag
下面我们要看遍历到范围,由于1不是素数,我们从2开始遍历,遍历到结束值是多少呢?两个数相加的结果为这个数,那一个数较小,另一个数较大,最中间的情况为两个数相等,因此我们只需要遍历到n//2 + 1。当找到一个较小的数是质数,并且较大的数也为质数,则可以满足条件了。
因此,我们可以将代码写成如下:
from math import sqrtdef is_prime(n): flag = True for i in range(2, int(sqrt(n)) + 1): if n % i == 0: flag = False break return flagn = int(input())for i in range(2, n // 2 + 1): if is_prime(i): if is_prime(n - i): print(i, n-i) break本题拓展
本题考查的是素数的判断和枚举算法,题目难度★★★★
除了验证哥德巴赫猜想外,还有一道与之相似的题目如下:
两个质数的和是 S,它们的积最大是多少?
输入格式
一个不大于 10000 的正整数 S,为两个质数的和。
输出格式
一个整数,为两个质数的最大乘积。数据保证有解。
输入样例
50
输出样例
589
前面验证哥德巴赫猜想的题目,我们只需要找出一个答案即可完成题目的要求。而部分数字可以拆分成多对质数的和,那哪一对质数的乘积是最大的呢?
我们需要从数学的知识里面知道和相等的数中哪一对乘积最大。从数学上可以证明出两个数最靠近时乘积最大。因此,这道题整体的思路与上面那道题基本相差不大,但是我们得换一个思路,从最中间的位置开始循环,让遍历到值依次变小。
from math import sqrtdef is_prime(n): flag = True for i in range(2, int(sqrt(n)) + 1): if n % i == 0: flag = False break return flagn = int(input())for i in range(n // 2, 1, -1): if is_prime(i): if is_prime(n - i): print(i * (n - i)) break
标签: #python求素数函数