有没有一个Python程序可以解半质数

Question

所以我有一个公式，解决半素数比每一对素数相乘一次又一次!因此，不用长时间猜测和检查(如下所示)，而是使用基本除法。

semi prime = 15 ... 2 * 3, 2 * 5, 2 * 7, 3 * 5 ... primes 3 and 5

and this is my way

semi prime = 15 ... 2 / 15, 3 / 15 ... primes ... primes 3 and 5

在这里不会改变长度，但在较大的半素数中会改变。但现在我想知道是否有一个python程序可以为我做这件事?到目前为止，我还不能制作一个，但我正在努力。

Answer 1

您想要的是对数字进行因式分解，这里有一个示例

def prime_generator(n):
    """produce all the prime numbers less or equal to n"""
    #put here the code for this
def prime_factorization(n):
    """return a list of with the all prime factors of n including their multiplicity""" 
    result=[]
    for p in prime_generator(n):
        while n%p==0: #while p divide n...
            result.append(p)
            n = n//p
        if n<=1:
            break
     return result
def is_semi_prime(n):
    factors = prime_factorization(n)   
    if len(factors) == 2:
        print n, "is a semi prime with those prime factors:", factors
    else:
        print n, "is not a semi-prime"
is_semi_prime( input("enter a number: ") )

这里有趣的部分是prime_generator它可以像用is_prime函数过滤数字一样简单，比如filter(is_prime,xrange(2,n+1))，或者更专业的东西，比如Eratostenes筛

编辑

上面使用一般方法来解决问题，可以通过专门的检查进一步改进，因为半素数只有两个因子，那么我们只需要找到第一个因子，从数字中删除它，如果剩下的是素数，我们就会找到它。为此，我们需要一个素数检验函数和一个素数生成器

def is_prime(n):
    #put here the code for this 

def prime_generator(n):
    #put here the code for this

def is_semi_prime(n):
    p1,p2 = 0,0
    for p1 in prime_generator(n):
        if n%p1==0:
            p2 = n//p1
            break
    if is_prime(p2):
        print n, "is a semi prime with those prime factors:", p1, p2
    else:
        print n, "is not a semi-prime"
is_semi_prime( input("enter a number: ") )

我认为这是你试图解释的算法，正如你所看到的，不需要搜索第二个素数(p2)，只需要搜索第一个素数(p1)，如果它存在，另一个将自然出现。

我把需要的两个函数留作练习。

对于is_prime，您可以像在答案中那样使用简单的试除，顺便说一下，它无法将2识别为素数，或者更强大的测试，如Miller-Rabin测试(确定性变体)(您可以在http://rosettacode.org中找到工作版本)或Baillie-PSW测试。

对于prime_generator，您可以使用，正如我之前提到的Eratostenes筛，或者使用无限素数生成器。例如，你可以在这个问题中找到如何:埃拉托色尼的筛子找到质数，以及如何在python中实现一个有效的无限质数生成器。后者是我最喜欢的

Answer 2

没关系，我想出来了。

import math
running = True
prime_1 = 0
prime_2 = 0
semi_prime = 0
n = 0
semi_prime = input('Enter Semi-Prime: ')
while running:
    if prime_1 * prime_2 == semi_prime:
        print('your 2 primes are')
        print([prime_1])
        print([prime_2])
        running = False
    else:
        n += 1
        def is_prime(number):
              if number < 2:
                    return False
              if number % 2 == 0:
                    return False
              else:
                    for i in range(3, number):
                          if not number % i:
                                return False
                    return True

        #This array stores all the prime numbers found till n
        primes = []
        for i in range(100000):
              if is_prime(i):
                    primes.append(i)
              if len(primes) == n:
                    break
        print("next prime is " + str(primes[n-1]))
        prime_1 = primes[n-1]
        prime_2 = semi_prime / primes[n-1]