Python

2024-01-07 00:56| 来源: 网络整理| 查看: 265

一.引言

给定任意一个大于10的偶数，寻找所有和为该偶数的质数对

二.实现 1.判断一个数字是否为质数

质数的定义是在大于1的自然数中，除了1和它本身不再有其他因数的自然数，所以判断 2 到 target - 1 之间的数字都无法整除，则该数为素数

# 寻找素数 2 -> target-1 都不能整除 def isPrime(num): is_prime = 1 for interval in range(2, num): if num % interval == 0: is_prime = 0 break return is_prime

2.寻找和为目标数字的质数对

对于一个偶数 target，可以有 2 + (target - 2)，3 + (target - 3) ，...，(target - 2) + 2 共 target - 2 种可能，判断这些可能中有没有满足 i + j = target 且 isPrime(i) == 1 and isPrime(j) == 1即可

def findPrimePair(num): result = [] # 判断是否是偶数 if num % 2 == 0: # 从2遍历到该偶数-1 for k in range(2, num): # k + (i - k) = 0 if isPrime(k) == 1 and isPrime(num - k) == 1: result.append("%d=%d+%d" % (num, k, num - k)) if len(result) == 0: print("%d has no prime pair!" % num) else: print("%d has %d prime pairs!" % (num, len(result))) print('\n'.join(result)) number = 500 findPrimePair(number) 500 has 26 prime pairs! 500=13+487 500=37+463 500=43+457 500=61+439 500=67+433 500=79+421 500=103+397 500=127+373 500=151+349 500=163+337 500=193+307 500=223+277 500=229+271 500=271+229 500=277+223 500=307+193 500=337+163 500=349+151 500=373+127 500=397+103 500=421+79 500=433+67 500=439+61 500=457+43 500=463+37 500=487+13

三.总结

第一步寻找质数过程中，假设因数 i * 因数 j = target ，则二者必然以 target / 2 为分界线，所以寻找范围可以缩减至 (2，target / 2)；同理，第二步寻找质数和中，假设质数 m + 质数 n = Target，则二者必然以 target / 2 为分界线，所以遍历范围可以缩减至 (2 ，target / 2 + 1)。

假设目标数为 200000000，修改前代码耗时 63984 ms，修改后耗时 10929 ms。

【本文地址】

公司简介

联系我们

今日新闻

推荐新闻

专题文章