Faster Way To Find Factors of n only using the math library

Question

Before you mark this as a duplicate...

I need to find the all the factors of n (which there are tons of solutions for). The fastest one I was able to implement was by looping through the range of 2 to sqrt of n. This is what I have thus far...

def get_factors(n):
    factors = set()
    for i in range(2, int(math.sqrt(n) + 1)):
        if n % i == 0:
            factors.update([i, n // i])
    return factors

This is a very fast method for finding the factors of n, but I am wondering if there is a faster way to find the factors of n. The only restriction I have is that I can only use the math library in Python 3.7. Any ideas on how this can be done faster? I couldn't find answers that only used the math library. Is there anything I can do to improve the efficency of my current algorithm?

Answer 1

EDIT: Just like @John Coleman said in the comment of this solution, it's better to obtain the factors while you're calculating the primes, so you can avoid extra work in case you finish factorizing the number before the sieve is finished. The updated code would be:

def factors(number):
    n=int(number**.5)+1
    x=number
    divisors=[]
    era =[1] * n
    primes=[]
    for p in range(2, n):
        if era[p]:
            primes.append(p)
            while x%p==0:
                x//=p
                divisors.append(p)
            for i in range(p*p, n, p):
                era[i] = False
    if x!=1:
        divisors.append(x)    
    return divisors

OG Solution:

Get the prime factors between 2 and sqrt(n) with the Erathostenes Sieve and after it, check which ones are divisors of n. That will reduce hugely the running time of your code.

The Erathostenes sieve doesn't use more than lists, operations %,>=,<= and booleans.

Here's a shorter implementation than the one in the link I shared you:

def factors(number):
    n=int(number**.5)+1
    era =[1] * n
    primes=[]
    for p in range(2, n):
        if era[p]:
            primes.append(p)
            for i in range(p*p, n, p):
                era[i] = False
    divisors=[]
    x=number
    for i in primes:
        while x%i==0:
            x//=i
            divisors.append(i)
    if x!=1:
        divisors.append(x)    
    return divisors