CODEWITHSUNDEEP
python
seVenVo1d
seVenVo1d

Reputation: 416

Integer factorization using Prime list (trying to find fastest algorithm)

from itertools import compress


def prime_number(n):
    sieve = bytearray([True]) * (n//2+1)
    for i in range(1,int(n**0.5)//2+1):
        if sieve[i]:
            sieve[2*i*(i+1)::2*i+1] = bytearray((n//2-2*i*(i+1))//(2*i+1)+1)
    return {2,*compress(range(3,n,2), sieve[1:])}


list_of_primes = prime_number(10**8)

def divisor_generator(num):
    '''Generates the divisiors of input num'''
    gen = []
    number = num
    for i in list_of_primes:
        while num % i == 0:
            if i < num //2:
                gen.append(num // i)
                gen.append(number // (num //i))
                num = num // i
            else:
                break
    return sorted([1, *gen, number])

In this code I am trying to create a fastest way to generate the divisors of a number by using prime numbers. I need to test the numbers up to 10**8. However divisor_generator function has some problems and its too slow. How can I increase the speed of my code

Upvotes: 0

Views: 52

Answers (1)

vurmux
vurmux

Reputation: 10020

You don't need to pre-calculate all prime numbers, it is far faster just to iterate through all possible divisors (even non-prime) from 2 to sqrt(N):

from math import sqrt

a = 1620
temp = a
divisors = []

# The largest possible divisor is equal to sqrt(a)
for i in range(2, int(sqrt(a)) + 1):
    while temp % i == 0:
        temp = temp // i
        divisors.append(i)
        print(i)
    if temp == 1:
        break
print(divisors)

[2, 2, 3, 3, 3, 3, 5]

Upvotes: 1

Related Questions