Is there a Python program that solves semi-primes?

Question

so i have a formula that solves semi-primes faster than multiplying every pair of prime numbers over and over again! so instead of having to use long guess and check(shown below) you use basic division.

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

it does not change the length a lot here but it does in larger semi-primes. but now i wonder if there is a python program that can do this for me ? so far i can not make one but i am working on it.

Answer 1

what you want is to factorize the number, here is a example of how

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: ") )

the funny part here is the prime_generator it can be as simple as just filtering the numbers with a is_prime function like for example filter(is_prime,xrange(2,n+1)), or something more specialized like the Sieve of Eratostenes

EDIT

the above which use a general approach to the problem can be further improve by specialized the check, as semi prime number only have exactly two factors then we only need to find the first, remove it from the number and if whatever remain is prime we find it. For that we need a prime checking function and a generator of primes

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: ") )

I think this is algorithm that you were trying to explain, as you can see don't need to search for the second prime (p2) only the first (p1) and the other will appear naturally if it exist.

I leave the two function needed as a exercise.

For is_prime you can use the simple trial division as you do in your answer which by the way fail to identify 2 as a prime, or a more powerful test like the Miller-Rabin test (Deterministic variants) (you can find a working version in http://rosettacode.org) or Baillie-PSW test.

For the prime_generator you can use, as I mention before the Sieve of Eratostenes, or make a use of a infinite prime generator. You can find how in for example this question: Sieve of eratosthenes finding primes python and how to implement an efficient infinite generator of prime numbers in python. The latter is my favorite

Answer 2

NEVER MIND, I FIGURED IT OUT.

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]