search

rlwhitcomb / utilities

Some of my personal utility programs
MIT License
2 stars 0 forks source link

Extend "factors" and "pfactors" to a larger range of numbers using Fermat's algorithm #613

Closed rlwhitcomb closed 7 months ago

rlwhitcomb commented 1 year ago

Since the largest prime factor of a number is floor(sqrt(n)) then we only need to do the prime sieve up to that value, so the biggest number we can actually factor is the limit of the sieve ** 2.

We can also use other known tricks to exclude small divisors (like adding up the digits, ending in 0 or 5, etc.)

rlwhitcomb commented 1 year ago

Actually, just defining MAX_PRIME as MAX_INT*MAX_INT and changing the check to n >= MAX_PRIME gives us primality and factoring up to 4,611,686,014,132,420,608 since we're already only testing up to the square root value of the input number anyway.

rlwhitcomb commented 7 months ago

So, depending on the factors of a number and its size, this could take a LONG time. But the limit where it starts to complain about oversize values is the 4 quintillion mark .... if that helps any.