Optimising Factoring Program

Question

This is my factorising code which is used to find all the factors of a number but after roughly 7 digits, the program begins to slow down.

so I was wondering if there is any method of optimising this program to allow it to factorise numbers faster.

number = int(input("Input the whole number here?\n"))
factors = [1]

def factorization():
    global factors
    for i in range(1 , number):
        factor = (number/i)
        try:
            factorInt = int(number/i)
            if factorInt == factor:
                factors.append(factorInt)
        except ValueError:
            pass


factorization()
print(factors)

Answer 1

The most effective optimization is by noting that when the number has non trivial factors, and the smallest of them is smaller than the square root of the number, and there is no need to continue looping past this square root.

Indeed, let this smallest factor be m. We have n = m.p and the other factor is such that p >= m. But if m > √n, then m.p >= n, a contradiction.

---

Note that this optimization only speeds-up the processing of prime numbers (for the composite ones, the search stops before √n anyway). But the density of primes and the fact that n is much larger than √n make it abolutely worth.

---

Another optimization is by noting that the smallest divisor must be a prime, and you can use a stored table of primes. (There are less than 51 million primes below one billion.) The speedup will be less noticeable.

Answer 2

Let me offer a NumPy-based solution. It seems quite efficient:

import numpy as np

def factorize(number):
    n = np.arange(2, np.sqrt(number), dtype=int)
    n2 = number / n
    low = n[n2.astype(int) == n2]
    return np.concatenate((low, number // low,))

factorize(34976237696437)
#array([     71,  155399, 3170053, 492623066147, 225073763,     11033329])])
# 176 msec