Fast Factorisation (Python Implementation)

Question

An algorithm for finding prime factors of a number given a list of all primes up to the square root of the number. It's worst case time complexity is \$O(n^{1/2})\$, the best case would be \$O(\log(n))\$, and I don't know how to calculate average case or amortised worst case. I am aware that this is not strictly optimal, but I think it is easier to understand and implement, than say Pollard's rho algorithm for prime factorisation (I suspect it works better if the number is composite with many prime factors as well). Suggestions for improvements are welcome.

FastFactorise.py

def fact(n): """ * Function to factorise a given number given a list of prime numbers up to the square root of the number. * Parameters: * `n`: The number to be factorised. * Return: * `res`: A dict mapping each factor to its power in the prime factorisation of the number. * Algorithm: * Step 1: Initialise `res` to an empty dictionary. * Step 2: If `n` > 1. * Step 3: Iterate through the prime number list. * Step 4: If ever the current prime number is > the floor of the square root of `n` + 1 exit the loop. * Step 5: If the current prime number is a factor of `n`. * Step 6: Assign 0 to `e`. * Step 7: While the current prime number is a factor of `n`. * Step 8: Increment `e`. * Step 9: Divide `n` by the current prime number. * [End of Step 7 while loop.] * Step 10: Map the current prime number to `e` in the result dictionary. * [End of step 5 if block.] * Step 11: If `n` is not 1 (after the repeated dividings) map `n` to 1 in the result dictionary. * Step 12: Return the result dictionary. * [Exit the function.] """ res = {} if n > 1: for p in primes: if p > int(sqrt(n)) + 1: break if n%p == 0: e = 0 while n%p == 0: e += 1 n //= p res[p] = e if n != 1: res[n] = 1 return res 

Answer 1

sqrt is expensive. You can avoid it by reworking your test condition from:

p > int(sqrt(n)) + 1 

to:

p*p > n 

---

You can skip one while n%p == 0 iteration by initializing e = 1 and unconditionally dividing by p once you’ve found a prime factor:

if n%p == 0: e = 1 n //= p while n%p == 0: # ...etc... 

---

Avoid putting “then” statements on the same line as the if statement: place the “then” statement indented on the next line.

---

The algorithm should be a comment, not part of the """docstring"""; callers generally only care about how to use the function, not the implementation details.