3
\$\begingroup\$

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
\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I am not to clear on proper docstring documentation. I was under the impression that it was for multiline comments? Your suggestion on phasing out sqrt() is apt, thanks (I applied the other fixes as well (I placed the algorithm above the function). \$\endgroup\$ – Tobi Alafin Feb 14 at 7:41
  • \$\begingroup\$ A triple-quoted string is string that can contain newlines & quotes without needing escapes. If the first statement in a function (or module/class) is a string (including a triple quoted one), it becomes the docstring for that entity. Eg) you can access your fact()’s docstring as fact.__docstring__ and it will return your text, verbatim. More importantly, a user could type help(fact) and retrieve the docstring formatted as a help string (some indentation is removed, extra info added). If you packaged the function in a module, help(mod_name) gives help for all functions in that module. \$\endgroup\$ – AJNeufeld Feb 14 at 18:40
  • \$\begingroup\$ The other way of getting rid of sqrt as accuracy is not needed is to do **0.5 \$\endgroup\$ – 13ros27 Feb 15 at 16:51
  • \$\begingroup\$ @13ros27 **0.5 is still doing slower, transcendental math, instead of simple multiplication which is not only exact, but is also much faster. (Also, **0.5 appears to be 8.8% slower than sqrt ... on my iPhone) \$\endgroup\$ – AJNeufeld Feb 15 at 18:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.