时间戳

首页 > 解决方案 > 检查素数和

python - 检查素数和

问题描述

下面的代码检查给定的整数是否可以表示为两个素数的和：

def sum_of_primes(num):
  isPrime = 1
  for i in range (2,int(num/2)+1):
    if(num % i == 0):
        isPrime = 0
        break
  return isPrime

num = [int(n) for n in input("Input the numbers: ").split()]

flag = 0
i = 2
for z in num:
  for i in range (2,int(z/2)+1):
    if(sum_of_primes(z) == 1):
      if(sum_of_primes(z-i) == 1):
         print(z,"can be expressed as a sum of",i,"and",z-i)
         flag = 1;
  if (flag == 0):
    print(z,"cannot be expressed as a sum of primes")

但是，我没有得到预期的结果：如果我输入[12 4 5]它会返回：

12 cannot be expressed as a sum of primes
4 can be expressed as a sum of 2 and 2
5 can be expressed as a sum of 2 and 3

它是错误的，因为 12 可以表示为7 + 5。应该为每个大于 2 的偶数工作。

如果输入是[5 4 12]它返回：

5 can be expressed as a sum of 2 and 3
4 can be expressed as a sum of 2 and 2

省略12。

标签： pythonpython-3.x

解决方案

如果您不需要产生实际的素数，而只测试是否存在一对素数 p 和 q 使得 p+q == N，您可以根据哥德巴赫猜想将其变得非常简单。所有偶数都可以表示为两个素数之和。因此，如果数字是偶数，则返回 True 并检查 N-2 是否是奇数的素数（因为 2 是唯一的偶素数，这是从奇数开始时会产生另一个奇数的唯一素数）。这将归结为仅对奇数进行 N-2 的单个素数测试。

def primePart(N):
    return N>3 and (N%2==0 or all((N-2)%p for p in range(3,int(N**0.5)+1,2)))

primePart(3432)  # True

primePart(37+2)  # True

primePart(13+41) # True

primePart(123)   # False

如果您确实需要找到实际的素数，那么您可以使用 Eratosthenes 的筛子将素数映射到 N 并依次检查对：

def primePart(N):
    isPrime = [0,0,1]+[1,0]*(N//2)      # sieve of Eratosthenes
    for p in range(3,int(N**0.5)+1,2):  # ... √N finds all primes up to N
        if isPrime[p]: isPrime[p*p::p] = [0]*len(isPrime[p*p::p])

    if N%2: return (2,N-2) if isPrime[N-2] else None # Odd number: prime + 2

    for p in range(3,N//2+1,2):  # find pair for even number
        if isPrime[p] and isPrime[N-p]: return (p,N-p)

print(primePart(3432))  # (19, 3413)

print(primePart(37+2))  # (2, 37)

print(primePart(13+41)) # (7, 43)

print(primePart(123))   # None

推荐阅读