Integer factorization in python

Question

I've seen on this website many way of doing integer factorizations in python, but didn't really understand them, so I tried to do it on my own way :

def factorisation(n):
fact = []
i = 2
while i<=n:     
    if n%i==0:      
        fact.append(i)
        n//= i
    else:
        i+=1
return fact

I think it is working, but I don't really know why the while loop from i to n ... From my lesson I learnt that we have to do if from 2 to sqrt(n). Did I misunderstand something ? Can I improve it ? Thanks :)

Answer 1

(This is mainly for the benefit of those like me who just want to get a prime factorisation, and not write one).

from sympy import factorint
factorint(216)
factorint(98316592849045095018623091009)

{2: 3, 3: 3}
{3: 2, 19: 3, 31: 2, 479: 2, 659: 4, 38299: 1}

The response a key of the primes used, with their value being the number of times they are used.

Answer 2

You only need to go to floor(sqrt(n)) if you are looking for smallest factor (such as in a primality test). if you want all the factors then you should check from 0 to n/2.

In short:

primality:

from math import sqrt

n = int(input('Please input a number: '))
sn = int(sqrt(n))
for x in range(2,sn+1):
    if n%x == 0:
        print('Not prime. Divisible by: '+str(x))
print(str(n)+' is prime')

factorization:

n = int(input('Please input a number: '))
n2 = int(n/2)
fn = []
for x in range(2,n2+1):
    if n%x == 0:
        fn.append(x) #lower member of factor pair
        fn.append(n/x) #upper member of factor pair
print('N has the following factors: '+str(fn))

I hope this helps you understand.

Answer 3

An example of using recursive call:

def factoring(x, print_eq=True):
    factors = []
    if x == 2:
        factors += [x]
    for i in range(2,x):
        if i*i > x:
            factors += [x]
            break
        if x%i == 0:
            factors += [i]
            factors += factoring(x//i, False)
            break
    # Factorization has been completed.
    # Print the result in pretty mode
    if print_eq:
        if x in factors:
            print(f'{x} = 1 * {x} is a prime')
        else:
            eq = ''
            nf = {i : factors.count(i) for i in factors}
            fs = list(sorted(nf))
            for i, f in enumerate(fs):
                if nf[f] > 1:
                    eq += f'{f}^{nf[f]}'
                else:
                    eq += f'{f}'
                if i < len(fs) - 1:
                    eq += ' * '
            print(f'{x} = {eq}\n')
    return factors

Some examples:

factoring(23756965471926357236576238546) gives

23756965471926357236576238546 = 2 * 3^2 * 479 * 11423 * 582677 * 413975744296733

[2, 3, 3, 479, 11423, 582677, 413975744296733]

factoring(1024) gives

1024 = 2^10

[2, 2, 2, 2, 2, 2, 2, 2, 2, 2]

factoring(137) gives

137 = 1 * 137 is a prime

[137]

Answer 4

This function with driver

def factors(n):
  global tmp
  answ=[]
  tmp=(n)
  addends=[4,2,4,2,4,6,2,6]
  def divn(dvr):
     
    
    global tmp
    while tmp%(dvr)==0:
      answ.append(dvr)
      tmp=tmp//dvr
       
  divn(2)
  divn(3)
  divn(5)
  d=(7)
  while (d)*(d)<=tmp:
     
    for i in range(8):
      divn(d)
      d=d+(addends[i])
  if tmp>1:
    answ.append(tmp)    
  return answ    
     
print(factors(23756965471926357236576238546))  

found

[2, 3, 3, 479, 11423, 582677, 413975744296733]

in 4 seconds. It does so by skipping over multiples of 2, 3 and 5 after testing those three primes. After testing for those three, it needs test only 8 out of every 30 numbers, starting with 7, in a cycle of addends given in the list of addends to the previously tested number. This cuts down on the number of non-primes used as a test. (30 is 235, so this constitutes the cycle of multiples of these).

Each tried number is tried as many times as needed until the remaining number is no longer divisible by it.

It uses a function within a function to try the actual division.

Answer 5

You can use Pollard's rho integer factorization algorithm. It's quite efficient and fast compared to other algorithms that are much slower. For example:

Python 3:

from math import gcd

def factorization(n):

    factors = []

    def get_factor(n):
        x_fixed = 2
        cycle_size = 2
        x = 2
        factor = 1

        while factor == 1:
            for count in range(cycle_size):
                if factor > 1: break
                x = (x * x + 1) % n
                factor = gcd(x - x_fixed, n)

            cycle_size *= 2
            x_fixed = x

        return factor

    while n > 1:
        next = get_factor(n)
        factors.append(next)
        n //= next

    return factors

With small numbers it's very fast, in this case it has taken only 0.035 seconds.

print(factorization(823767))

~$ time python3 factorization.py
[3, 7, 39227]

real    0m0,035s
user    0m0,031s
sys     0m0,004s

If we use slightly larger numbers the calculation time increases, but it's still very fast, in this case just 0.038 seconds.

print(factorization(41612032092))

~$ time python3 factorization.py
[3, 4, 37, 1681, 127, 439]

real    0m0,038s
user    0m0,034s
sys     0m0,004s

And if we use very large numbers it takes a little more time, but it's still a very reasonable time considering that it's a huge number. In this case just 28.128 seconds.

print(factorization(23756965471926357236576238546))

~$ time python3 factorization.py
[3, 3, 2, 479, 11423, 582677, 413975744296733]

real    0m28,128s
user    0m28,120s
sys     0m0,008s

I hope it helps you. Greetings.

Answer 6

When an integer n is not divisible by any number up to sqrt(n), that is sufficient to indicate that n is prime. In that case you won't find any additional factors other than n itself.

So what you can do is to stop the loop at sqrt(n), and add the remaining value of n to the list of prime factors.