1
\$\begingroup\$

Compute the prime factors of a given natural number. A prime number is only evenly divisible by itself and 1. Note that 1 is not a prime number.

My solution will catch every prime up to and including 896803. This is the fastest solution I could come up with. I know that hard code can only go so far.

def prime_factors(n):
    factors = []
    found_last_factor = False
    if n == 1: return factors
    if is_prime(n): return [n]
    while found_last_factor == False: 
        for f in range(2, int(n/2+1)):
            if n % f == 0 and is_prime(f):
                n /= f
                factors.append(f)
                if is_prime(n): 
                    factors.append(n)
                    found_last_factor = True
                    break
    return sorted(factors)

def is_prime(f: int) -> bool:
    if f is 1: return False
    for n in (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 
            61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 
            137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 
            199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 
            277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 
            359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 
            439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 
            521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 
            607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 
            683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 
            773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 
            863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947):
        if f == n: return True
        elif f % n == 0: return False
        elif f / n < n: return True
\$\endgroup\$
2
  • 1
    \$\begingroup\$ A test case that can be timed would be good, when you care about the fastest code. \$\endgroup\$ – Janne Karila Oct 13 '18 at 20:49
  • \$\begingroup\$ Please see What to do when someone answers. I have rolled back Rev 4 → 3. \$\endgroup\$ – 200_success Oct 14 '18 at 19:36
5
\$\begingroup\$
    while found_last_factor == False:

Style is subjective, but I know I'm not the only develop who considers comparisons to Boolean literals to be bad style. while not found_last_factor: is an alternative which I consider preferable.


There are various inefficiencies in this code:

    while found_last_factor == False:
        for f in range(2, int(n/2+1)):
            if n % f == 0 and is_prime(f):
                n /= f
                factors.append(f)
                if is_prime(n): 
                    factors.append(n)
                    found_last_factor = True
                    break
    return sorted(factors)
  1. If it were modified to handle repeated prime factors in an inner loop rather than in the outmost loop then
    1. The test is_prime(f) would be unnecessary, because n % f == 0 would already imply the primality of f.
    2. Primes would be discovered in order, removing the need to call sorted.
    3. A lot of unnecessary iterations of f would be saved. You rebutted AJNeufeld's observation on this subject, so consider an alternative perspective: add a line print(f) at the top of the for f loop, and then call prime_factors(1024).
  2. The call to is_prime(n) tests primality by trial division, and is called from a loop which is factoring n by trial division. That's duplication of both code and run time.

/= does floating point division. Use //= for integer division. Similarly int(n/2+1) could be n//2 + 1.

\$\endgroup\$
2
  • \$\begingroup\$ I'm not sure how to fix your second point. The value of n changes. It wouldn't make sense to loop up to it if I could just check it right there with is_prime(n), \$\endgroup\$ – Tony J Oct 14 '18 at 18:30
  • \$\begingroup\$ You can take some of the reasoning used in is_prime and pull it into prime_factors: namely that when f * f > n either n is prime or n is 1. That's a sufficient condition to break. \$\endgroup\$ – Peter Taylor Oct 14 '18 at 19:58
3
\$\begingroup\$

is_prime() can terminate without returning a value (returning None) if the input is large, but not divisible by a prime under 1000. You should handle that explicitly (perhaps raise an exception).

Bug? prime_factors(45) will return [3,5], but 3*5 != 45. You might want to handle factors like \$p^n\$, where p is a prime. Update Ok, not a bug. (I didn't run the code with an official interpreter; just my eyeball interpreter, which is a bit buggy.) The while loop around the for loop will eventually catch that the repeated primes. Still, you're doing a lot of extra work when you could just keep factoring out the prime factor. If that is done, then you don't need the outer while loop.

Your loop for f in range(2, int(n/2+1)): does not update the end point as n gets smaller with successive factors being found. In the case of 45, it loops up to 22, despite finding the last factor of 5 seventeen iterations earlier.

\$\endgroup\$
3
  • \$\begingroup\$ prime_factors(45) gives me [3, 3, 5]. I ran the code in the debugger and it did not do any extra loops. \$\endgroup\$ – Tony J Oct 13 '18 at 21:26
  • 1
    \$\begingroup\$ Actually, given 45 it returns [3, 3.0, 5] \$\endgroup\$ – Peter Taylor Oct 13 '18 at 22:03
  • \$\begingroup\$ @PeterTaylor I fixed that \$\endgroup\$ – Tony J Oct 13 '18 at 22:24

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.