Algorithm to find Largest prime factor of a number

Question

What is the best approach to calculating the largest prime factor of a number   I m thinking the most efficient would be the following    Find lowest prime number that divides cleanly Check if result of division is prime If not  find next lowest Go to 2    I m basing this assumption on it being easier to calculate the small prime factors  Is this about right  What other approaches should I look into   Edit  I ve now realised that my approach is futile if there are more than 2 prime factors in play  since step 2 fails when the result is a product of two other primes  therefore a recursive algorithm is needed   Edit again  And now I ve realised that this does still work  because the last found prime number has to be the highest one  therefore any further testing of the non-prime result from step 2 would result in a smaller prime

User · Answer

The simplest solution is a pair of mutually recursive functions   The first function generates all the prime numbers    Start with a list of all natural numbers greater than 1  Remove all numbers that are not prime  That is  numbers that have no prime factors  other than themselves   See below    The second function returns the prime factors of a given number n in increasing order    Take a list of all the primes  see above   Remove all the numbers that are not factors of n    The largest prime factor of n is the last number given by the second function   This algorithm requires a lazy list or a language  or data structure  with call-by-need semantics   For clarification  here is one  inefficient  implementation of the above in Haskell   import Control Monad  -- All the primes primes   2   filter  ap   lt     head   primeFactors    3 5     -- Gives the prime factors of its argument primeFactors   factor primes   where factor    n              factor xs  p ps  n             if p p  gt  n then  n            else let  d r    divMod n p in             if r    0 then p   factor xs d             else factor ps n  -- Gives the largest prime factor of its argument largestFactor   last   primeFactors   Making this faster is just a matter of being more clever about detecting which numbers are prime and or factors of n  but the algorithm stays the same

User · Answer

It seems to me that step  2 of the algorithm given isn t going to be all that efficient an approach   You have no reasonable expectation that it is prime   Also  the previous answer suggesting the Sieve of Eratosthenes is utterly wrong   I just wrote two programs to factor 123456789   One was based on the Sieve  one was based on the following   1   Test   2  2   Current   Number to test  3   If Current Mod Test   0 then   3a      Current   Current Div Test  3b      Largest   Test 3c      Goto 3   4   Inc Test   5   If Current  lt  Test goto 4 6   Return Largest   This version was 90x faster than the Sieve   The thing is  on modern processors the type of operation matters far less than the number of operations  not to mention that the algorithm above can run in cache  the Sieve can t   The Sieve uses a lot of operations striking out all the composite numbers   Note  also  that my dividing out factors as they are identified reduces the space that must be tested

User · Answer

Python Iterative approach by removing all prime factors from the number  def primef n       if n  lt   3          return n     if n   2    0          return primef n 2      elif n   3   0          return primef n 3      else          for i in range 5  int  n   0 5    1  6                print i             if n   i    0                  return primef n i              if n    i   2     0                  return primef n  i 2       return n

User · Answer

I think it would be good to store somewhere all possible primes smaller then n and just iterate through them to find the biggest divisior  You can get primes from prime-numbers org   Of course I assume that your number isn t too big

User · Answer

n   abs number   result   1  if  n mod 2    0      result   2    while  n mod 2   0  n    2    for i 3  i lt sqrt n   i  2      if  n mod i    0        result   i      while  n mod i   0   n    i        return max n result    There are some modulo tests that are superflous  as n can never be divided by 6 if all factors 2 and 3 have been removed  You could only allow primes for i  which is shown in several other answers here   You could actually intertwine the sieve of Eratosthenes here    First create the list of integers up to sqrt n   In the for loop mark all multiples of i up to the new sqrt n  as not prime  and use a while loop instead  set i to the next prime number in the list    Also see this question

User · Answer

All numbers can be expressed as the product of primes  eg   102   2 x 3 x 17 712   2 x 2 x 2 x 89   You can find these by simply starting at 2 and simply continuing to divide until the result isn t a multiple of your number   712   2   356    356   2   178    178   2   89    89   89   1   using this method you don t have to actually calculate any primes  they ll all be primes  based on the fact that you ve already factorised the number as much as possible with all preceding numbers   number   712  currNum   number        the value we ll actually be working with for  currFactor in 2    number        while  currNum   currFactor    0               keep on dividing by this number until we can divide no more          currNum   currNum   currFactor        reduce the currNum           if  currNum    1  return currFactor        once it hits 1  we re done

User · Answer

My answer is based on Triptych s  but improves a lot on it  It is based on the fact that beyond 2 and 3  all the prime numbers are of the form 6n-1 or 6n 1    var largestPrimeFactor  if n mod 2    0        largestPrimeFactor   2      n   n   2 while n mod 2    0     if n mod 3    0        largestPrimeFactor   3      n   n   3 while n mod 3    0      multOfSix   6  while multOfSix - 1  lt   n        if n mod  multOfSix - 1     0                largestPrimeFactor   multOfSix - 1          n   n   largestPrimeFactor while n mod largestPrimeFactor    0              if n mod  multOfSix   1     0                largestPrimeFactor   multOfSix   1          n   n   largestPrimeFactor while n mod largestPrimeFactor    0             multOfSix    6      I recently wrote a blog article explaining how this algorithm works    I would venture that a method in which there is no need for a test for primality  and no sieve construction  would run faster than one which does use those  If that is the case  this is probably the fastest algorithm here

User · Answer

With Java   For int values   public static int   primeFactors int value        int   a   new int 31       int i   0  j      int num   value      while  num   2    0            a i      2          num    2            j   3      while  j  lt   Math sqrt num    1            if  num   j    0                a i      j              num    j            else               j    2                      if  num  gt  1            a i      num            int   b   Arrays copyOf a  i       return b      For long values   static long   getFactors long value        long   a   new long 63       int i   0      long num   value      while  num   2    0            a i      2          num    2            long j   3      while  j  lt   Math sqrt num    1            if  num   j    0                a i      j              num    j            else               j    2                      if  num  gt  1            a i      num            long   b   Arrays copyOf a  i       return b

User · Answer

Actually there are several more efficient ways to find factors of big numbers  for smaller ones trial division works reasonably well     One method which is very fast if the input number has two factors very close to its square root is known as Fermat factorisation  It makes use of the identity N    a   b  a - b    a 2 - b 2 and is easy to understand and implement  Unfortunately it s not very fast in general   The best known method for factoring numbers up to 100 digits long is the Quadratic sieve  As a bonus  part of the algorithm is easily done with parallel processing   Yet another algorithm I ve heard of is Pollard s Rho algorithm  It s not as efficient as the Quadratic Sieve in general but seems to be easier to implement     Once you ve decided on how to split a number into two factors  here is the fastest algorithm I can think of to find the largest prime factor of a number   Create a priority queue which initially stores the number itself  Each iteration  you remove the highest number from the queue  and attempt to split it into two factors  not allowing 1 to be one of those factors  of course   If this step fails  the number is prime and you have your answer  Otherwise you add the two factors into the queue and repeat

User · Answer

Found this solution on the web by  James Wang   public static int getLargestPrime  int number         if  number  lt   1  return -1       for  int i   number - 1  i  gt  1  i--            if  number   i    0                number   i                      return number

User · Answer

JavaScript code    option strict    function largestPrimeFactor val  divisor   2         let square    val    gt  Math pow val  2        while   val   divisor     0  amp  amp  square divisor   lt   val            divisor               return square divisor   lt   val           largestPrimeFactor val   divisor  divisor            val      Usage Example   let result   largestPrimeFactor 600851475143     Here is an example of the code

User · Answer

Here is the same function Triptych provided as a generator  which has also been simplified slightly    def primes n       d   2     while  n  gt  1           while  n d  0               yield d             n    d         d    1   the max prime can then be found using   n  373764623 max primes n     and a list of factors found using   list primes n

User · Answer

I m aware this is not a fast solution  Posting as hopefully easier to understand slow solution    public static long largestPrimeFactor long n                largest composite factor must be smaller than sqrt         long sqrt    long Math ceil Math sqrt  double n             long largest   -1           for long i   2  i  lt   sqrt  i                  if n   i    0                    long test   largestPrimeFactor n i                   if test  gt  largest                        largest   test                                                     if largest    -1                return largest                        number is prime         return n

User · Answer

The following C   algorithm is not the best one  but it works for numbers under a billion and its pretty fast   include  lt iostream gt  using namespace std      ------ is prime ------    Determines if the integer accepted is prime or not bool is prime int n       int i count 0      if n  1    n  2        return true      if n 2  0        return false      for i 1 i lt  n i         if n i  0          count              if count  2        return true      else       return false         ------ nextPrime -------     Finds and returns the next prime number  int nextPrime int prime        bool a   false       while  a    false            prime             if  is prime prime               a   true           return prime         ----- M A I N ------  int main           int value   13195        int prime   2        bool done   false         while  done    false             if  value prime    0                value   value prime               if  is prime value                     done   true                             else                prime   nextPrime prime                               cout  lt  lt   Largest prime factor     lt  lt  value  lt  lt  endl

User · Answer

I am using algorithm which continues dividing the number by it s current Prime Factor   My Solution in python 3    def PrimeFactor n       m   n     while n 2  0          n   n  2     if n    1            check if only 2 is largest Prime Factor          return 2     i   3     sqrt   int m   0 5      loop till square root of number     last   0                to store last prime Factor i e  Largest Prime Factor     while i  lt   sqrt           while n i    0              n   n  i         reduce the number by dividing it by it s Prime Factor             last   i         i  2     if n gt  last               the remaining number n  is also Factor of number          return n     else          return last print PrimeFactor int input         Input   10 Output   5  Input   600851475143  Output   6857

User · Answer

Prime factor using sieve      include  lt bits stdc   h gt  using namespace std   define N 10001   typedef long long ll  bool visit N   vector lt int gt  prime   void sieve                 memset  visit   0   sizeof visit                for  int i 2 i lt N i                                   if  visit i     0                                        prime push back i                       for  int j i 2  j lt N  j j i                                                 visit j    1                                                             void sol long long n  vector lt int gt  amp prime                ll ans   n              for int i 0  i lt prime size      prime i  gt n  i                                  while n prime i   0                                        n n prime i                       ans   prime i                                               ans   max ans  n               cout lt  lt ans lt  lt endl    int main                 ll tc  n             sieve                cin gt  gt n             sol n  prime               return 0

User · Answer

Compute a list storing prime numbers first  e g  2 3 5 7 11 13      Every time you prime factorize a number  use implementation by Triptych but iterating this list of prime numbers rather than natural integers

User · Answer

This is probably not always faster but more optimistic about that you find a big prime divisor    N is your number If it is prime then return N  Calculate primes up until Sqrt N  Go through the primes in descending order  largest first    If N is divisible by Prime then Return Prime     Edit  In step 3 you can use the Sieve of Eratosthenes or Sieve of Atkins or whatever you like  but by itself the sieve won t find you the biggest prime factor   Thats why I wouldn t choose SQLMenace s post as an official answer

User · Answer

Here is my attempt in c   The last print out is the largest prime factor of the number  I checked and it works   namespace Problem Prime     class Program         static void Main string   args                        The prime factors of 13195 are 5  7  13 and 29         What is the largest prime factor of the number 600851475143                   long x   600851475143        long y   2        while  y  lt  x                  if  x   y    0                         y is a factor of x  but is it prime           if  IsPrime y                           Console WriteLine y                         x    y                     y                   Console WriteLine y         Console ReadLine              static bool IsPrime long number                check for evenness       if  number   2    0                  if  number    2                      return true                    return false                  don t need to check past the square root       long max    long Math Sqrt number         for  int i   3  i  lt   max  i    2                  if   number   i     0                      return false                          return true

User · Answer

Here is my attempt in Clojure  Only walking the odds for prime  and the primes for prime factors ie  sieve  Using lazy sequences help producing the values just before they are needed     Sieve of Eratosthenes  defn sieve   i  amp  is  as ps  n       let  q  quot n i            r  mod n i        cond  zero  r       lazy-seq  cons i  sieve ps q                gt     i i  n   when   gt  n 1   lazy-seq  n               else          recur is n       defn prime       n       let  oddNums  iterate       2  3            is       cons 2 oddNums        prime  n is        n  i  amp  is        let  q  quot n i            r  mod n i        cond   lt  n 2        false            zero  r      false             gt     i i  n  true            else          recur n is        def primes     let  oddNums  iterate       2  3      lazy-seq  cons 2  filter prime  oddNums        defn max-prime-factor  n     last  sieve primes n

User · Answer

python implementation import math n   600851475143 i   2 factors set     while i lt math sqrt n      while n i  0         n n i        factors add i     i  1 factors add n  largest max factors  print factors print largest

User · Answer

Here is my approach to quickly calculate the largest prime factor  It is based on fact that modified x does not contain non-prime factors  To achieve that  we divide x as soon as a factor is found  Then  the only thing left is to return the largest factor  It would be already prime   The code  Haskell    f max  x i   i  gt  x   max               x  rem  i    0   f i  x  div  i  i  -- Divide x by its factor              otherwise   f max  x  i   1   -- Check for the next possible factor  g x   f 2 x 2

User · Answer

include lt stdio h gt   include lt conio h gt   include lt math h gt   include  lt time h gt   factor long int n    long int i j  while n gt  4     if n 2  0     n n 2    i 2        else    i 3  j 0    while j  0         if n i  0      j 1     n n i          i i 2       i- 2        return i       void main         clock t start   clock      long int n sp    clrscr      printf  enter value of n      scanf   ld   amp n     sp factor n     printf  largest prime factor is  ld  sp      printf  Time elapsed   f n     double clock   - start    CLOCKS PER SEC     getch

User · Answer

Here s the best algorithm I know of  in Python     def prime factors n          Returns all the prime factors of a positive integer        factors          d   2     while n  gt  1          while n   d    0              factors append d              n    d         d   d   1      return factors   pfs   prime factors 1000  largest prime factor   max pfs    The largest element in the prime factor list   The above method runs in O n  in the worst case  when the input is a prime number    EDIT  Below is the O sqrt n   version  as suggested in the comment  Here is the code  once more   def prime factors n          Returns all the prime factors of a positive integer        factors          d   2     while n  gt  1          while n   d    0              factors append d              n    d         d   d   1         if d d  gt  n              if n  gt  1  factors append n              break     return factors   pfs   prime factors 1000  largest prime factor   max pfs    The largest element in the prime factor list

User · Answer

Not the quickest but it works       static bool IsPrime long num                long checkUpTo    long Math Ceiling Math Sqrt num            for  long i   2  i  lt   checkUpTo  i                          if  num   i    0                  return false                    return true

User · Answer

this method skips unnecessary trial divisions and makes        trial division more feasible for finding large primes      public static void main String   args                 long n  1000000000039L    this is a large prime number          long i   2L          int test   0           while  n  gt  1                        while  n   i    0                                n    i                                  i                 if i i  gt  n  amp  amp  n  gt  1                                 System out println n     prints n if it s prime                 test   1                  break                                   if  test    0                System out println i-1     prints n if it s the largest prime factor

User · Answer

Calculates the largest prime factor of a number using recursion in C    The working of the code is explained below   int getLargestPrime int number        int factor   number     assumes that the largest prime factor is the number itself     for  int i   2   i i   lt   number  i         iterates to the square root of the number till it finds the first smallest  factor         if  number   i    0       checks if the current number i  is a factor             factor   max i  number   i      stores the larger number among the factors             break     breaks the loop on when a factor is found                     if  factor    number     base case of recursion         return number      return getLargestPrime factor      recursively calls itself

User · Answer

Similar to  Triptych answer but also different  In this example list or dictionary is not used  Code is written in Ruby  def largest prime factor number    i   2   while number  gt  1     if number   i    0       number    i      else       i    1     end   end   return i end  largest prime factor 600851475143      gt  6857

[algorithm] Algorithm to find Largest prime factor of a number

Examples related to algorithm

Examples related to math

Examples related to prime-factoring