检查一个数字是否可以划分为质数分区

Question

有人可以在 Python 上解决这个问题吗？

一个正整数m可以被划分为质数，如果它可以写成p + q，其中p > 0，q > 0并且p和q都是质数。

编写一个 Python 函数，将整数 m 作为输入，如果 m 可以划分为素数，则 returns 为真，否则为假。

试过这个，但不适用于所有测试用例，例如它应该 return 对 3432 为真，它 return 为假。

def partition(num):
    primelist=[]
    for i in range(2,num + 1):
        for p in range(2,i):
            if (i % p) == 0:
                break
        else:
            primelist.append(i)


    for x in primelist:
        y= num-x
        for z in range(2,y):
            if y%z == 0:
                return False

        return True

Answer 1

错误在第二个for循环。您正在遍历可能的素数 x，然后希望检查 y = num - x 是否也是素数。

你的逻辑错误是在第二个for循环中，如果循环中的第一个元素y = num - x不是质数，它会return False，而不检查任何其他可能的值。

您可以通过将 return False 语句移出一个循环来更正此问题，但是由于您已经生成了一个小于 num、primelist 的素数列表（并且由于 y = num - x，（如果素数 y 存在）它将在此列表中），您可以只检查列表的成员：

    for x in primelist:
        y= num-x
        # Note: num = x + y, thus need only check y prime
        if y in primelist:
            return True
        # If no such y is prime, not possible
        else:
            return False

注意：我建议使脚本的逻辑更加模块化，将素数列表生成器分离到它自己的函数中：

def partition(num):
    """
    Return True if there exist primes x,y such that num = x + y.
    Else return False.
    """
    primelist = primes(num)
    for x in primelist:
        y= num-x
        # Note: num = x + y, thus need only check y prime
        if y in primelist:
            return True
    # If no such y is prime, not possible
    else:
        return False

def primes(num):
    """Return list of all primes less than num."""
    primelist=[]
    for i in range(2,num + 1):
        for p in range(2,i):
            if (i % p) == 0:
                break
        else:
            primelist.append(i)
    return primelist

Answer 2

我得到的最终解决方案：

def primepartition(m):
    primelist=[]
    if m<0:
        return False
    else:
        for i in range(2,m + 1):
            for p in range(2,i):
                if (i % p) == 0:
                    break
            else:
                primelist.append(i)

        for x in primelist:
            y= m-x
            if y in primelist:
                return True
        return False

Answer 3

您的代码略有变化：

def primepartition0(m):
    primelist=[]
    if m<0:
        return False
    else:
        for i in range(2,m + 1):
            for p in range(2,i):
                if (i % p) == 0:
                    break
            else:
                primelist.append(i)

        for x in primelist:
            for y in primelist:
                if x != y and x+y == m:
                    return True
        return False

Answer 4

下面给出的代码有望为您提供正确的输出。

def factors(n):
    factorslist = []
    for i in range(1, n+1, 1):
        if n % i == 0:
            factorslist.append(i)
    return(factorslist)    

def prime(n):
    if factors(n) == [1, n] and n > 1:
        return(True)

def primelist(n):
    primenolist = []
    for i in range(1, n+1, 1):
        if prime(i) == True:
            primenolist.append(i)
    return(primenolist)

def primepartition(m):
    if m > 0:
        primenolist = primelist(m)
        checklist = []
        for p in primenolist:
            q = m - p
            if q in primenolist and p > 0 and q > 0:
                checklist.append((p,q))
        if len(checklist) > 0:
            return(True)
        else:
            return(False)
    else:
        return(False)

Answer 5

尝试减少所需代码量的替代方法：

def primepartition(m):
    if m > 3:
        for number in range(m // 2, m - 1):
            difference = m - number

            for psuedoprime in range(2, int(number ** 0.5) + 1):
                if number % psuedoprime == 0 or difference > psuedoprime and difference % psuedoprime == 0:
                    break
            else:  # no break
                return number, difference  # as good a non-False result as any other...

    return False

Answer 6

另一种方法，最初，我们将所有素数元素存储到 m 并检查其和等于 m

的素数对

def primepartition(a):
l=[2]#since 'a' should be >=2 for below loops, we took here 2(1st prime).
for i in range(2,a):
        flag=0
        for j in range(2,i):
            if i%j==0:
                flag=0
                break
            else:
                flag=1
        if flag==1:
            l.append(i)
for i in l:
    for j in l:
        if i+j==a:
            return True
return False

Answer 7

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

def primePart(N):
    return 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

如果你想真正找到一对加起来为 N 的素数，你可以生成最多为 N 的素数并且 return 第一个素数 >= N/2 其中 N - 素数是一个已找到的素数：

def findPQ(N):
    if not primePart(N): return
    if N%2: return 2,N-2
    isPrime = [0]+[1]*N
    for p in range(3,N,2):
        if not isPrime[p]: continue
        if 2*p>=N and isPrime[N-p]: return p,N-p
        isPrime[p*p::p] = [0]*len(isPrime[p*p::p])

输出：

findPQ(3432)      # (1723, 1709)

findPQ(12345678)  # (6172879, 6172799)

要超越 10^9，您将需要比埃拉托色尼筛法更快的内存效率更高的算法。这可以通过要跳过的素数倍数的字典来实现：

def findPQ(N):
    if not primePart(N): return
    if N%2: return 2,N-2
    skip,primes = {},{2}
    for p in range(3,N,2):
        if p in skip:
            prime = skip.pop(p)
            mult  = p + 2*prime
            while mult in skip: mult += 2*prime
            if mult <= N: skip[mult] = prime
        else:
            if 2*p>=N and N-p in primes: return p,N-p
            if p*p<=N: skip[p*p]=p
            if 2*p<=N: primes.add(p)

输出（需要一段时间但不会破坏内存 space）：

findPQ(1234567890)  # (617283983, 617283907)

Answer 8

def factors(n):
    factlist = []
    for i in range(1,n+1):
        # Since factors of 2 cannot be primes, we ignore them.
        if n%i==0 and i%2!=0:
            factlist.append(i)
    return factlist

def isprime(n):
    return(factors(n)==[1,n])

def preimesupto(n):
    primelist = []
    if n>=2:
        primelist.append(2)
    for i in range(n):
        if isprime(i):
            primelist.append(i)
    return primelist

def primepartition(n):
    if n<0:
        return False
    primelist = preimesupto(n)
    for i in primelist:
        j = n-i
        if j in primelist:
            return True
    else:
        return False

Answer 9

def checkprime(number):
fact=1
for r in range(2,number):
if number%r==0:
  fact=fact+1
return(fact<2)

def primepartition(m):

for i in range(2,m):

flag=0
if checkprime(i) and checkprime(m-i)==True:
  flag=1
  break
return(flag==1)

def matched(s):
list_of_string=list(s)
for y in range(len(list_of_string)):
if list_of_string[y]=='(':
for z in range(y,len(list_of_string)):
    if list_of_string[z]==')':
      list_of_string[y]='@'
      list_of_string[z]='@'
      break
 return('('not in list_of_string and ')'not in list_of_string)

 def rotatelist(l,k):
 if k>len(l):
 k=int(k%len(l))
 return(l[k:]+l[0:k])

Answer 10

n=int(input("Enter any number: "))
list=[]
for num in range(0,n + 1):  
 if num > 1:  
     for i in range(2,num):  
       if (num % i) == 0:  
           break  
       else:
           list.append(num)
if (n<= 1):
    print("False")
    #print("It is not positive ")
else:
    for i in list:
        y = num -i
        if (y in list):
            print("True")
            #print(y,"+",i,"=",n)
            #print(i,"+",y,"=",n)
            #print("The number can be expressed as the sum of two prime numbers.")
            break
    else:
        print("False")
        #print("The number can not be expressed as the sum of two prime numbers.")

检查一个数字是否可以划分为质数分区

Check if a number can be divided into prime partitions

python

python-3.x

partition-problem