Prime factorization python

Question

I'm very new to python, and I thought that I would create a program that returns the prime factors of a given number. This is my code:

import math
import operator
import functools

def isprime (n):
    if n == 1:
        return False
    elif n == 2:
        return True
    else:
        for x in range (2, int(math.sqrt(n))+1):
            if n % x == 0:
                return False
                break
        else:
            return True



def factors (a):
    factorlist = []
    if isprime(a) == True:
        print "The number is a prime."
    else:   
        while functools.reduce(operator.mul, factorlist, 1) != a:
            for x in range (1, a):
                if a % x == 0:
                    if isprime(x) == True:
                        factorlist.append(x)
        factorlist.sort()
        print factorlist

testnumber = int(input("Enter a number."))
factors(testnumber)

My problem is that depending on the number, it takes a very long time. It can solve 100 or 1000 instantly, but 2000 or 864 just doesn't work! I left it running with 864 as my input for 45 minutes, but it didn't print anything. Is is something with the quality of my CPU? I'm running the program on a laptop.

Factorizing large numbers is a hard problem. It is so hard that popular cryptography algorithms are built around it. So don't expect your naive program to solve this efficiently. — Ferdinand Beyer, Feb 07 '15 at 13:09
You might want to replace "if isprime(a) == True" with "if isprime(a)" - Python makes a call to the reduce function in the functools library with each iteration in the while loop, this can take a very long time so you might want to replace it with something faster - Also check if there's an infinite loop by putting print statements in your code - Change the for loop in your while loop into a list comprehension, That should make the code much much more faster and more readable, Good Luck — no_name, Feb 07 '15 at 13:20

score 3 · Answer 1 · answered Feb 07 '15 at 13:21

Your problem definitely isn't the complexity for numbers as small as 864. Rather, when you do this:

while functools.reduce(operator.mul, factorlist, 1) != a:
    for x in range (1, a):
        ...

What you're doing is essentially going through all possible prime numbers every time it doesn't reduce. This is redundant, as you only need to go through the list once anyway.

And for input such as 2000, you enter an infinite loop because it'll never reduce to 2000 - that's why it just keeps running. You can add print factorlist between the while and for to see exactly what's happening.

If you just remove the while statement, you'll be able to get the results much faster.

(Do note that I agree with Ferdinand Beyer's comment about large numbers above. I'm just saying that in your specific case, 864 isn't a large number, and there's a bug in your program.)

score 1 · Answer 2 · edited May 23 '17 at 10:33

1

Here is a fastest one;

n = 600851475143 
i = 2

while i * i < n:
    while n%i == 0:
        n /= i
        print (i)
    i += 1

You can find the explanation of this method in here. n is the number and i prime factors.

edited May 23 '17 at 10:33

Community

1
1

answered Feb 07 '15 at 13:51

GLHF

3,835
10
38
83

score 1 · Accepted Answer · answered Feb 07 '15 at 14:37

The problems with your code are that you're repeatedly doing some expensive computation in the call functools.reduce(operator.mul, factorlist, 1) and that you're repeatedly checking isprime(x) for the same numbers (and isprime is itself expensive because of the loop).

To avoid the functools.reduce call you can simply divide out the already known factors by mutating the number you're factoring as in @howaboutNO's solution, or by making a recursive call (see below).

To avoid the expense of calling isprime(x) with the same values you can use memoization, which is a handy trick to have in your toolset.

Applying both of these, I came up with the following:

import math

def memoize(f):
    memo = {}
    def helper(x):
        if x not in memo:
            memo[x] = f(x)
        return memo[x]
    return helper

@memoize
def isprime (n):
    if n == 1:
        return False
    elif n == 2:
        return True
    else:
        for x in range (2, int(math.sqrt(n))+1):
            if n % x == 0:
                return False
                break
        else:
            return True


def factors (a):
    if a == 1:
        return []
    elif isprime(a):
        return [a]
    else:
        for x in range (2, int(math.sqrt(a))+1):
            if a % x == 0:
                return [x] + factors(a/x)

testnumber = int(input("Enter a number."))
print factors(testnumber)

which runs much more quickly than your code.

score 1 · Answer 4 · answered Feb 07 '15 at 16:09

Here is a faster factorization based on a modular sieve:

# modular sieve based on (2,3,5):
sieve_size = 2 * 3 * 5
sieve = [1, 7, 11, 13, 17, 19, 23, 29]

# all primes < sieve_size
base = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

def factors(a):
    f = []

    # remove factors of primes < sieve_size
    for b in base:
        while not a % b:
            a //= b
            f.append(b)
        if a < b*b:
            break

    # remnant fully factored?
    if a < b*b:
        if a > 1:
            f.append(a)
        return f

    # remove factors of values generated by modular sieve
    #   (We do not need to test for actual primality;
    #   because candidate values are generated in ascending order,
    #   if the value is composite, all factors of it will have
    #   already been removed)
    n = sieve_size
    while True:
        for s in sieve:
            b = n + s      # 31, 37, 41, 43, ...
            while not a % b:
                a //= b
                f.append(b)
            if a < b*b:
                break
        if a < b*b:
            if a > 1:
                f.append(a)
            return f
        n += sieve_size

and then a quick test:

import random
for i in range(30):
    val = random.randint(1000, 1000000)
    print(val, factors(val))

which almost immediately gives

344779 [73, 4723]
376343 [11, 34213]
830823 [3, 7, 39563]
927157 [7, 11, 12041]
852641 [852641]
802619 [47, 17077]
80214 [2, 3, 29, 461]
348030 [2, 3, 3, 3, 5, 1289]
533572 [2, 2, 13, 31, 331]
317206 [2, 199, 797]
806636 [2, 2, 421, 479]
539294 [2, 7, 7, 5503]
706820 [2, 2, 5, 59, 599]
501587 [97, 5171]
759410 [2, 5, 75941]
375319 [7, 53617]
668889 [3, 3, 13, 5717]
545731 [545731]
496852 [2, 2, 124213]
309332 [2, 2, 17, 4549]
629728 [2, 2, 2, 2, 2, 11, 1789]
835342 [2, 417671]
505591 [71, 7121]
172411 [172411]
410995 [5, 13, 6323]
645451 [31, 47, 443]
369849 [3, 113, 1091]
67237 [71, 947]
505186 [2, 11, 22963]
945547 [945547]

score 0 · Answer 5 · answered Apr 01 '20 at 10:40

0

Unless you're doing it as a programming exercise, just use

primefactors(testnumber)

answered Apr 01 '20 at 10:40

Michael Greaney

21
3

Prime factorization python

5 Answers5