[Coding Project]-Prime Factorization Algorithm

[AvgStudent]

I'm starting a side coding project. The objective of the project is to factorize large integers. My experience has always been with relatively small integers and done by hand. For those numbers, I would divide them by the smallest prime number that goes into it evenly with no remainder. Continue this process with each number I get until I reach 1.

However, I think this process is very inefficient with larger integers like 13197. I'm looking for a more efficient way to do prime factorization. Thanks

 

[Cubist]

I'm starting a side coding project. The objective of the project is to factorize large integers. My experience has always been with relatively small integers and done by hand. For those numbers, I would divide them by the smallest prime number that goes into it evenly with no remainder. Continue this process with each number I get until I reach 1.

However, I think this process is very inefficient with larger integers like 13197. I'm looking for a more efficient way to do prime factorization. Thanks

13197 seems like a very small integer for modern computers to deal with. However I understand your intent, that you probably want to write efficient code that would cope with large inputs in a reasonable time.

There's a Unix command called "factor". On my very old computer the following command takes only 0.3s...

factor 139328741993027404241335422061
139328741993027404241335422061: 8056300032617 17294383455052133

The "GNU factor" code is available for download, and there's probably documentation about how it works around the internet. I think it used to use a technique called wheel factorisation (click). I think it uses a new (faster?) algorithm nowadays. I looked into it some time ago myself (out of interest). However, that might be beyond the scope of your project.

Sometimes I find it off-putting to know that other projects have achieved brilliant results. I think, "I can't compete with this, so why should I bother starting". But I recommend that you do go for it and start off small/ simple. This is how we learn!

 

[AvgStudent]

13197 seems like a very small integer for modern computers to deal with. However I understand your intent, that you probably want to write efficient code that would cope with large inputs in a reasonable time.

There's a Unix command called "factor". On my very old computer the following command takes only 0.3s...

factor 139328741993027404241335422061
139328741993027404241335422061: 8056300032617 17294383455052133

The "GNU factor" code is available for download, and there's probably documentation about how it works around the internet. I think it used to use a technique called wheel factorisation (click). I think it uses a new (faster?) algorithm nowadays. I looked into it some time ago myself (out of interest). However, that might be beyond the scope of your project.

Sometimes I find it off-putting to know that other projects have achieved brilliant results. I think, "I can't compete with this, so why should I bother starting". But I recommend that you do go for it and start off small/ simple. This is how we learn!

Thanks for the info. I'll see what I can do.

 

[AvgStudent]

Took your advice I took the first step. I wrote the algorithm I described in the OP. It works fairly well for n<=13 digits. It takes approximately 0.2s to return. My computer started to freeze for n>13 digits. The next step is to look into your wheel factorization technique.

Here's my code if anyone is interested.

Spoiler: Code

# Returns the smallest factor of n.
def smallest_prime_factor(n):
    assert n>=2
    for i in range(2,n,1):
        if n % i ==0:
            return i
    return n #Return n if n is prime itself

#Prime factorization.
def prime_factors(n):
    prime_list = []
    while True:
        p = smallest_prime_factor(n)
        prime_list.append(p)
        if p < n:
            n //= p
        else:
            return prime_list

#Test
print(prime_factors(9851485143955))

#Output
[5, 7, 13, 17, 97, 127, 103387]

 

[Cubist]

Great start!

If you want basic initial advice for speeding this up...

Spoiler

If checking the number 17 for prime factors, then you're going through...
2,3,4,5,6...,13,14,15,16

Why not stop at sqrt(17)...
2,3,4

5 or more can't be possible because 5*5=25, and you've already checked 4,3,2 so 4*5,3*5,2*5 aren't possible

Note python has a built in function...
import math
math.isqrt(n)

 

[AvgStudent]

Great start!

If you want basic initial advice for speeding this up...

Spoiler

If checking the number 17 for prime factors, then you're going through...
2,3,4,5,6...,13,14,15,16

Why not stop at sqrt(17)...
2,3,4

5 or more can't be possible because 5*5=25, and you've already checked 4,3,2 so 4*5,3*5,2*5 aren't possible

Note python has a built in function...
import math
math.isqrt(n)

Thank you for the idea! I found out that it's called the primality test. While working on the project, I also found something called the Sieve of Eratosthenes (sounds like Greek!), which is an ancient algorithm to find primes up to a given limit. Real cool.

​