Python Finding Prime Factors

by

This question was the first link that popped up when I googled "python prime factorization".
As pointed out by @quangpn88, this algorithm is wrong (!) for perfect squares such as n = 4, 9, 16, ... However, @quangpn88’s fix does not work either, since it will yield incorrect results if the largest prime factor occurs 3 or more times, e.g., n = 2*2*2 = 8 or n = 2*3*3*3 = 54.

I believe a correct, brute-force algorithm in Python is:

def largest_prime_factor(n):
    i = 2
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
    return n

Don’t use this in performance code, but it’s OK for quick tests with moderately large numbers:

In [1]: %timeit largest_prime_factor(600851475143)
1000 loops, best of 3: 388 µs per loop

If the complete prime factorization is sought, this is the brute-force algorithm:

def prime_factors(n):
    i = 2
    factors = []
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors.append(i)
    if n > 1:
        factors.append(n)
    return factors

More Related Contents:

  1. code that check if number is prime number [duplicate]
  2. Fastest way to list all primes below N
  3. How to implement an efficient infinite generator of prime numbers in Python?
  4. Sieve of Eratosthenes – Finding Primes Python
  5. Simple prime number generator in Python
  6. isPrime Function for Python Language
  7. Print series of prime numbers in python
  8. Prime number check acts strange [duplicate]
  9. To find first N prime numbers in python
  10. Adding wheel factorization to an indefinite sieve
  11. Fastest-in term of space- way to find prime numbers with python
  12. Sieve of Eratosthenes – Primes between X and N
  13. code that count the amount of yes and no in a list [closed]
  14. How to use asyncio with threading in Python is Method threading.Timer
  15. Add to list in python if list is value in dictionary [closed]
  16. Can a lambda function call itself recursively in Python?
  17. How can I bundle other files when using cx_freeze?
  18. stop / start / pause in python matplotlib animation
  19. How can I open a website with urllib via proxy in Python?
  20. setup.py and adding file to /bin/
  21. Get output from a Paramiko SSH exec_command continuously
  22. Python windows path slash [duplicate]
  23. Conda command not found
  24. overriding bool() for custom class [duplicate]
  25. Sorting list by an attribute that can be None
  26. How to convert PIL Image.image object to base64 string? [duplicate]
  27. Nested list comprehension scope
  28. Python: is using “..%(var)s..” % locals() a good practice?
  29. Identifying the data type of an input
  30. matplotlib imshow – default colour normalisation

Leave a Comment