时间戳

首页 > 解决方案 > 在 Python 中检查一个数字是否可以表示为两个半素数之和

python - 在 Python 中检查一个数字是否可以表示为两个半素数之和

问题描述

半素数是可以表示为两个素数的乘积的数。例子：55 = 5 * 11

我正在尝试编写一个 Python 程序来检查一个数字是否可以表示为两个半素数的总和（不一定不同）。

示例 1：

  输入：30
  输出：是

解释：30 可以表示为 15 + 15，其中 15 是一个半素数，因为它是两个素数 5 * 3 的乘积。

示例 2：

  输入：62
  输出：否

解释：虽然，62 本身是一个半素数（31 * 2），但是它不能表示为两个半素数之和。

这是我尝试做的，但并非在所有情况下都有效。

MAX = 200
arr = []
sprime = [False] * (MAX)

def computeSP():
    for i in range(2,MAX):
        cnt,num,j = 0,i,2
        while (cnt<2 and j*j <= num):
            while(num % j == 0):
                num = int(num/j)
                cnt = cnt + 1
            j = j+1

        if(num > 1):
            cnt = cnt + 1

        if(cnt == 2):
            sprime[i] = True
            arr.append(i)

def checkSP(n):
    i = 0
    while(arr[i] <= n/2):
        if(sprime[n - arr[i]]):
            return True
        i = i+1
    return False

computeSP()

n = int(input())

if(checkSP(n)):  
    print('Yes',end='')  
else:
    print('No',end='')

标签： python

解决方案

在您提到的情况下，62 可以表示为 2 个半素数之和，即 58 和 4 即 62 = 58+4 58 可以表示为 29,2 的因数（素数） 4 可以表示为 2 的因数， 2（质数）

因此，回答你的问题是你的逻辑是错误的，因为 62 也可以用类似的方式表示。

如果你想要代码，那么你去：

import math
def factors(n):
    bool = False
    for i in range(2, n):
        if n % i == 0:
            a = i
            b = int(n / a)
            if prime_number(a) and prime_number(b):
                print("factors of ",n,"is",a,b)
                bool = True
                break
    return bool


def prime_number(m):
    prime = True
    for i in range(3, m):
        if m % i == 0:
            prime = False
            break
    return prime


if __name__ == '__main__':
    num = int(input())
    z = math.ceil(num/2)
    a = "NO"
    for i in range(1, z):
        x = i
        y = num - i
    if factors(x) and factors(y):
        print("diff x,y=", x, y)
        a = "YES"
        break
print(a)

推荐阅读