Python Finding Prime Factors

Question

Two part question   1  Trying to determine the largest prime factor of 600851475143  I found this program online that seems to work  The problem is  I m having a hard time figuring out how it works exactly  though I understand the basics of what the program is doing  Also  I d like if you could shed some light on any method you may know of finding prime factors  perhaps without testing every number  and how your method works   Here s the code that I found online for prime factorization  NOTE  This code is incorrect  See Stefan s answer below for better code     n   600851475143 i   2 while i   i  lt  n       while n   i    0           n   n   i      i   i   1  print  n    takes about  0 01secs   2  Why is that code so much faster than this code  which is just to test the speed and has no real purpose other than that   i   1 while i  lt  100      i    1  takes about  3secs

User · Answer

Another way of doing this   import sys n   int sys argv 1   result      for i in xrange 2 n       while n   i    0           print i     n         n   n i         result append i       if n    1           break  if n  gt  1  result append n  print result   sample output   python test py 68  2  2  17

User · Answer

For prime number generation I always use Sieve of Eratosthenes   def primes n       if n lt  2          return        sieve  True   n 1      for x in range 3 int n  0 5  1 2           for y in range 3  n  x  1 2               sieve  x y   False      return  2   i for i in range 3 n 2  if sieve i    In  42    timeit primes 10  5  10 loops  best of 3  60 4 ms per loop  In  43    timeit primes 10  6  1 loops  best of 3  1 01 s per loop   You can use Miller-Rabin primality test to check whether a number is prime or not  You can find its Python implementations here   Always use timeit module to time your code  the 2nd one takes just 15us   def func        n   600851475143     i   2     while i   i  lt  n           while n   i    0              n   n   i          i   i   1  In  19    timeit func   1000 loops  best of 3  1 35 ms per loop  def func        i 1     while i lt 100 i  1                In  21    timeit func   10000 loops  best of 3  15 3 us per loop

User · Answer

Another way that skips even numbers after 2 is handled   def prime factors n      factors         d      2    step   1    while d d  lt   n        while n gt 1           while n d    0              factors append d              n   n d         d    step         step   2    return factors

User · Answer

Below are two ways to generate prime factors of given number efficiently   from math import sqrt   def prime factors num               This function collectes all prime factors of given number and prints them              prime factors list          while num   2    0          prime factors list append 2          num    2     for i in range 3  int sqrt num   1  2           if num   i    0              prime factors list append i              num    i     if num  gt  2          prime factors list append int num       print sorted prime factors list     val   int input  Enter number     prime factors val    def prime factors generator num               This function creates a generator for prime factors of given number and generates the factors until user asks for them      It handles StopIteration if generator exhausted              while num   2    0          yield 2         num    2     for i in range 3  int sqrt num   1  2           if num   i    0              yield i             num    i     if num  gt  2          yield int num    val   int input  Enter number     prime gen   prime factors generator val  while True      try          print next prime gen       except StopIteration          print  Generator exhausted              break     else          flag   input  Do you want next prime factor    y  or  n             if flag     y               continue         elif flag     n               break         else              print  Please try again and enter a correct choice i e  either y or n

User · Answer

n int input  Enter the number    if n  1     because the below logic doesn t work on 1     print n  for i in range 2   n 1       if n i  0           n1 i   get factor         for b in range 2 n 1    check if it is prime             if   n1 b   0   amp   n1  b                   print n1              elif  n1 b   0 or n1 lt b    if not then pass                 break   i am sure this is the worst logic but it s all the knowledge i have in  py this program will get a number from user and prints all of it s factors numbers that are prime like for 12 it will give 2 3

User · Answer

The prime factors of 13195 are 5  7  13 and 29   What is the largest prime factor of the number 600851475143         from sympy import primefactors print primefactors 600851475143  -1

User · Answer

My code     METHOD  PRIME FACTORS def prime factors n          PRIME FACTORS  generates a list of prime factors for the number given     RETURNS  number being factored   list prime factors   count how many loops to find factors  for optimization              num   n                          number at the end     count   0                        optimization  to count iterations      index   0                        index  to test      t    2  3  5  7                  list  to test      f                                prime factors list     while t index     2  lt   n          count    1                   increment  how many loops to find factors          if len t      index   1               t append t -2    6       extend test list  as much as needed   2  3  5  7  11  13             if n   t index               if 0 does else  otherwise increments  or try next t index               index    1               increment index         else              n   n    t index         drop max number we are testing     this should drastically shorten the loops              f append t index         append factor to list     if n  gt  1          f append n                   add last factor        return num  f  f count optimization   count     Which I compared to the code with the most votes  which was very fast      def prime factors2 n           i   2         factors              count   0                            added to test optimization         while i   i  lt   n              count    1                       added to test optimization             if n   i                  i    1             else                  n     i                 factors append i          if n  gt  1              factors append n          return factors  f count   count      print with  count added    TESTING   note  I added a COUNT in each loop to test the optimization      gt  gt  gt  prime factors2 600851475143      71  839  1471  6857    count  1472      gt  gt  gt  prime factors 600851475143     600851475143   71  839  1471  6857    count optimization  494     I figure this code could be modified easily to get the  largest factor  or whatever else is needed  I m open to any questions  my goal is to improve this much more as well for larger primes and factors

User · Answer

The code is wrong with 100  It should check case i   i   n    I think it should be   while i   i  lt   n      if i   i   n          n   i         break      while n i    0          n   n   i     i   i   1  print  n

User · Answer

Isn t largest prime factor of 27 is 3    The above code might be fastest but it fails on 27 right   27   3 3 3 The above code returns 1 As far as I know     1 is neither prime nor composite  I think  this is the better code  def prime factors n       factors        d 2     while d d lt  n           while n gt 1                           while n d  0                  factors append d                  n n d             d  1     return factors -1

User · Answer

def prime n       for i in range 2 n           if n i  0              return False     return True  def primefactors        m int input  enter the number         for i in range 2 m           if  prime i                if m i  0                  print i      return print  end of it    primefactors

User · Answer

You shouldn t loop till the square root of the number  It may be right some times  but not always   Largest prime factor of 10 is 5  which is bigger than the sqrt 10   3 16  aprox    Largest prime factor of 33 is 11  which is bigger than the sqrt 33   5 5 74  aprox    You re confusing this with the propriety which states that  if a number has a prime factor bigger than its sqrt  it has to have at least another one other prime factor smaller than its sqrt  So  with you want to test if a number is prime  you only need to test till its sqrt

User · Answer

This is my python code   it has a fast check for primes and checks from highest to lowest the prime factors   You have to stop if no new numbers came out   Any ideas on this     import math   def is prime v3 n           Return  true  if n is a prime number   False  otherwise         if n    1          return False      if n  gt  2 and n   2    0          return False      max divisor   math floor math sqrt n       for d in range 3  1   max divisor  2           if n   d    0              return False     return True   number    lt Number gt   for i in range 1 math floor number 2        if is prime v3 i           if number   i    0              print  Found     with factor     format number   i  i     The answer for the initial question arrives in a fraction of a second

User · Answer

Check this out  it might help you a bit in your understanding    program to find the prime factors of a given number import sympy as smp  try      number   int input  Enter a number       except ValueError        print  Please enter an integer     num   number prime factors      if smp isprime number        prime factors append number  else       for i in range 2  int number 2    1                  while figuring out prime factors of a given number  n         keep in mind that a number can itself be prime or if not           then all its prime factors will be less than or equal to its int n 2   1             if smp isprime i  and number   i    0               while number   i    0                    prime factors append i                  number   number    i print  prime factors of     str num      -    for i in prime factors       print i  end

User · Answer

It looks like people are doing the Project Euler thing where you code the solution yourself  For everyone else who wants to get work done  there s the primefac module which does very large numbers very quickly     python  import primefac import sys  n   int  sys argv 1    factors   list  primefac primefac n    print   n  join map str  factors

User · Answer

Since nobody has been trying to hack this with old nice reduce method  I m going to take this occupation  This method isn t flexible for problems like this because it performs loop of repeated actions over array of arguments and there s no way how to interrupt this loop by default  The door open after we have implemented our own interupted reduce for interrupted loops like this   from functools import reduce  def inner func func  cond  x  y       res   func x  y      if not cond res           raise StopIteration x  y      return res  def ireducewhile func  cond  iterable         generates intermediary results of args while reducing     iterable   iter iterable      x   next iterable      yield x     for y in iterable          try              x   inner func func  cond  x  y          except StopIteration              break         yield x   After that we are able to use some func that is the same as an input of standard Python reduce method  Let this func be defined in a following way   def division c       num  start   c     for i in range start  int num  0 5  1           if num   i    0              return  num  i  i      return None   Assuming we want to factor a number 600851475143  an expected output of this function after repeated use of this function should be this    600851475143  2  - gt   8462696833 - gt  71    10086647 - gt  839    6857  1471  - gt  None   The first item of tuple is a number that division method takes and tries to divide by the smallest divisor starting from second item and finishing with square root of this number  If no divisor exists  None is returned  Now we need to start with iterator defined like this   def gener prime         returns and infinite generator  600851475143  2   0  0  0        yield  prime  2      while True          yield 0   Finally  the result of looping is   result   list ireducewhile lambda x y  div x   lambda x  x is not None  iterable gen 600851475143     result    600851475143  2    8462696833  71    10086647  839    6857  1471     And outputting prime divisors can be captured by   if len result     1  output   result 0  0  else  output   list map lambda x  x 1   result 1      result -1  0    output   2  71  839  1471    Note   In order to make it more efficient  you might like to use pregenerated primes that lies in specific range instead of all the values of this range

User · Answer

num list       def primeFactors n       for i in range 2 n   1           while n   i    0              num list append i              n   n   i         if n    1              break n   13195 primeFactors n  print num list

User · Answer

def find prime facs n     list of factors      i 2   while n gt 1      if n i  0        list of factors append i        n n i       i i-1     i  1     return list of factors

User · Answer

If you are looking for pre-written code that is well maintained  use the function sympy ntheory primefactors from SymPy  It returns a sorted list of prime factors of n   gt  gt  gt  from sympy ntheory import primefactors  gt  gt  gt  primefactors 6008   2  751   Pass the list to max   to get the biggest prime factor  In case you want the prime factors of n and also the multiplicities of each of them  use sympy ntheory factorint   Given a positive integer n  factorint n  returns a dict containing the prime factors of n as keys and their respective multiplicities as values    gt  gt  gt  from sympy ntheory import factorint  gt  gt  gt  factorint 6008      6008    2  3     751  1   2  3  751  1   The code is tested against Python 3 6 9 and SymPy 1 1 1

User · Answer

Ok  So you said you understand the basics  but you re not sure EXACTLY how it works  First of all  this is a great answer to the Project Euler question it stems from  I ve done a lot of research into this problem and this is by far the simplest response   For the purpose of explanation  I ll let n   20  To run the real Project Euler problem  let n   600851475143   n   20  i   2  while i   i  lt  n      while n i    0          n   n   i     i   i   1  print  n    This explanation uses two while loops  The biggest thing to remember about while loops is that they run until they are no longer true    The outer loop states that while i   i isn t greater than n  because the largest prime factor will never be larger than the square root of n   add 1 to i after the inner loop runs    The inner loop states that while i divides evenly into n  replace n with n divided by i  This loop runs continuously until it is no longer true  For n 20 and i 2  n is replaced by 10  then again by 5  Because 2 doesn t evenly divide into 5  the loop stops with n 5 and the outer loop finishes  producing i 1 3   Finally  because 3 squared is greater than 5  the outer loop is no longer true and prints the result of n   Thanks for posting this  I looked at the code forever before realizing how exactly it worked  Hopefully  this is what you re looking for in a response  If not  let me know and I can explain further

User · Answer

In case you want to use numpy here s a way to create an array of all primes not greater than n     i  for i in np arange 2 n 1   if 0 not in np array  i     i-2      np arange 2 i

User · Answer

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  lt   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  lt   n          if n   i              i    1         else              n     i             factors append i      if n  gt  1          factors append n      return factors

[python] Python Finding Prime Factors

Examples related to python

Examples related to primes