most efficient algorithm to calculate prime factors of many numbers in the range up to ~ 10^9

45 Views Asked by At

I need to calculate prime factorizations of numbers in the range up to ~ 10^9. I evaluate ~ 10^5 to 10^6 numbers, most of them large, i.e. 10^8 .. 10^9.

I am interested in numbers with small prime factors only, i.e. in the range 2 .. 300; all others do not pass my test. Therefore I do not evaluate the complete prime factorization but stop if remaining factors are larger than 300, even if these factors are not prime but contain prime factors > 300.

The code of the function reads as follows:

    def calc_prime_factors(self, n):                
    factors = []  
    if (n == 1):                # no further checks on data type and range
        factors.append(1)       # I don't want to return an empty list
        return factors
    for p in Primes._primes:    # precalculated primes [2, 3 ... ~300] at class level
        if (p**2 > n):
            break
        while (n % p == 0):
            factors.append(p)
            n = n // p
    if (n > 1):
        factors.append(n)       # last factor may not be prime, but exceed limit i.e. 300
    return factors    

I tried several Python libraries but none is as fast as this implementation.

Original questions: Is there any way to improve this code? Are there alternative algorithms that might be faster?

In the meantime I tried caching of factorizations but the hit rate with ~ 0.01 is very low; performance is slightly decreased (I guess due to cache overhead).

The numbers to be factored are generated as numerator and denominator of neighbored Farey fractions of fixed Farey order. If the denominator is smaller than a previously checked Farey order, the entire factorization and test is skipped. Therefore, the numbers are neither consecutive nor sorted nor random. The mechanism to generate the numbers cannot be changed.

So the original question remains the same.

0

There are 0 best solutions below