How to find all factors of a huge number which is of only a few factors in less than 1 second?

Question

For example, the number is 3000000021 whose prime factors are 3 and 1000000007.

In a traditional way, e.g.

n=int(raw_input())
d=2
factors=[]
while n!=1:
    if n%d==0:
        factors.append(d)
        n/=d
    else:
        d+=1
print factors

It takes forever to analyze such number.

Pollard's Rho algorithm seems to be a good solution in this case, but it can't get all of them. Is there any faster way to solve this problem?

[This link should solve your problem](http://stackoverflow.com/questions/6800193/what-is-the-most-efficient-way-of-finding-all-the-factors-of-a-number-in-python) — whackamadoodle3000, May 13 '17 at 13:07
This seems like a pretty standard problem; did you look *anywhere* for a solution? — Scott Hunter, May 13 '17 at 13:08
You could start by not testing every even integer greater than 2. — Scott Hunter, May 13 '17 at 13:09
Possible duplicate of [What is the most efficient way of finding all the factors of a number in Python?](http://stackoverflow.com/questions/6800193/what-is-the-most-efficient-way-of-finding-all-the-factors-of-a-number-in-python) — Laurent LAPORTE, May 13 '17 at 13:09
an approach using `bitarray`: http://stackoverflow.com/a/31122596/4954037 — hiro protagonist, May 13 '17 at 13:11

AChampion · Answer 1 · 2017-05-13T14:30:46.417

Even a very simple factors() function which has a simple optimisation of limiting to sqrt(n)+1, completes in sub 1s

In [1]:
def factors(n):
    for a in range(2, int(n**0.5)+1):
        if n % a:
            continue
        yield from {a, n//a}

In [2]:
list(factors(3000000021))

Out[2]:
[3, 1000000007]

In [3]:
%timeit list(factors(3000000021))

Out[3]:
100 loops, best of 3: 6.69 ms per loop

If you only need prime factors then you need an efficient prime number generator (lots of examples can be found on SO) then:

In [4]:
def pfactors(n):
    for p in primes():
        while n % p == 0:
            yield p
            n //= p
        if p*p > n:
            if n > 1:
                yield n
            break

list(pfactors(3000000021))

Out[4]:
[3, 1000000007]

The speed of this is dependent on your prime number generator. For my python prime number generator:

In [5]:
%timeit list(pfactors(3000000021))

Out[5]:
100 loops, best of 3: 6.13 ms per loop

score 0 · Answer 2 · answered Apr 11 '22 at 17:20

credit goes to Evgeni Sergeev

from sympy import factorint
factorint(3000000021)

#output
{3: 1, 1000000007: 1}

factorint returns a dictionary where you can get all the prime factors by

list(factorint(3000000021).keys())
#Prime factors of 3000000021:
[3, 1000000007]

each key shows the prime factor while each value shows the power of corresponding prime factor in dictionary

How to find all factors of a huge number which is of only a few factors in less than 1 second?

2 Answers2