math - Algorithm to find Largest prime factor of a number


Translate

What is the best approach to calculating the largest prime factor of a number?

I'm thinking the most efficient would be the following:

  1. Find lowest prime number that divides cleanly
  2. Check if result of division is prime
  3. If not, find next lowest
  4. 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.


All Answers
  • Translate

    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.


  • Translate

    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 > 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 > 1:
            while n % d == 0:
                factors.append(d)
                n /= d
            d = d + 1
            if d*d > n:
                if n > 1: factors.append(n)
                break
        return factors
    
    
    pfs = prime_factors(1000)
    largest_prime_factor = max(pfs) # The largest element in the prime factor list
    

  • Translate

    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 <= 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.


  • Translate

    JavaScript code:

    'option strict';
    
    function largestPrimeFactor(val, divisor = 2) { 
        let square = (val) => Math.pow(val, 2);
    
        while ((val % divisor) != 0 && square(divisor) <= val) {
            divisor++;
        }
    
        return square(divisor) <= val
            ? largestPrimeFactor(val / divisor, divisor)
            : val;
    }
    

    Usage Example:

    let result = largestPrimeFactor(600851475143);
    

    Here is an example of the code:


  • Translate

    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 > 1
        if number % i == 0
          number /= i;
        else
          i += 1
        end
      end
      return i
    end
    
    largest_prime_factor(600851475143)
    # => 6857
    

  • Translate

    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.
    }
    

  • Translate
        //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 > 1)
            {
                while (n % i == 0)
                {
                    n /= i;     
                }
    
                i++;
    
                if(i*i > n && n > 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
        }
    

  • Translate

    The simplest solution is a pair of mutually recursive functions.

    The first function generates all the prime numbers:

    1. Start with a list of all natural numbers greater than 1.
    2. 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.

    1. Take a list of all the primes (see above).
    2. 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 (<=) (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 > 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.


  • Translate
    n = abs(number);
    result = 1;
    if (n mod 2 == 0) {
      result = 2;
      while (n mod 2 = 0) n /= 2;
    }
    for(i=3; i<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.


  • Translate

    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 <= sqrt; i++) {
                if(n % i == 0) {
                    long test = largestPrimeFactor(n/i);
                    if(test > largest) {
                        largest = test;
                    }
                }
            }
    
            if(largest != -1) {
                return largest;
            }
    
            // number is prime
            return n;
        } 
    

  • Translate

    Python Iterative approach by removing all prime factors from the number

    def primef(n):
        if n <= 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
    

  • Translate

    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 <= 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> 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


  • Translate

    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 < 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 <= max; i += 2)
          {
            if ((number % i) == 0)
            {
              return false;
            }
          }
          return true;
        }
    
      }
    }
    

  • Translate
    #python implementation
    import math
    n = 600851475143
    i = 2
    factors=set([])
    while i<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
    

  • Translate

    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) <= 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
    }
    

  • Translate

    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 > 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
    

  • Translate

    The following C++ algorithm is not the best one, but it works for numbers under a billion and its pretty fast

    #include <iostream>
    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<=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 << "Largest prime factor: " << value << endl;
     }
    

  • Translate

    Found this solution on the web by "James Wang"

    public static int getLargestPrime( int number) {
    
        if (number <= 1) return -1;
    
        for (int i = number - 1; i > 1; i--) {
            if (number % i == 0) {
                number = i;
            }
        }
        return number;
    }
    

  • Translate

    Prime factor using sieve :

    #include <bits/stdc++.h>
    using namespace std;
    #define N 10001  
    typedef long long ll;
    bool visit[N];
    vector<int> prime;
    
    void sieve()
    {
                memset( visit , 0 , sizeof(visit));
                for( int i=2;i<N;i++ )
                {
                    if( visit[i] == 0)
                    {
                        prime.push_back(i);
                        for( int j=i*2; j<N; j=j+i )
                        {
                            visit[j] = 1;
                        }
                    }
                }   
    }
    void sol(long long n, vector<int>&prime)
    {
                ll ans = n;
                for(int i=0; i<prime.size() || prime[i]>n; i++)
                {
                    while(n%prime[i]==0)
                    {
                        n=n/prime[i];
                        ans = prime[i];
                    }
                }
                ans = max(ans, n);
                cout<<ans<<endl;
    }
    int main() 
    {
               ll tc, n;
               sieve();
    
               cin>>n;
               sol(n, prime);
    
               return 0;
    }
    

  • Translate

    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 < 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.


  • Translate

    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.


  • Translate

    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 <= Math.sqrt(num) + 1) {
            if (num % j == 0) {
                a[i++] = j;
                num /= j;
            } else {
                j += 2;
            }
        }
        if (num > 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 <= Math.sqrt(num) + 1) {
            if (num % j == 0) {
                a[i++] = j;
                num /= j;
            } else {
                j += 2;
            }
        }
        if (num > 1) {
            a[i++] = num;
        }
        long[] b = Arrays.copyOf(a, i);
        return b;
    }
    

  • Translate

    This is probably not always faster but more optimistic about that you find a big prime divisor:

    1. N is your number
    2. If it is prime then return(N)
    3. Calculate primes up until Sqrt(N)
    4. 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...)


  • Translate

    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 :)


  • Translate

    Not the quickest but it works!

        static bool IsPrime(long num)
        {
            long checkUpTo = (long)Math.Ceiling(Math.Sqrt(num));
            for (long i = 2; i <= checkUpTo; i++)
            {
                if (num % i == 0)
                    return false;
            }
            return true;
        }
    

  • Translate

    Here is the same function@Triptych provided as a generator, which has also been simplified slightly.

    def primes(n):
        d = 2
        while (n > 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))
    

  • Translate
    #include<stdio.h>
    #include<conio.h>
    #include<math.h>
    #include <time.h>
    
    factor(long int n)
    {
    long int i,j;
    while(n>=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",&n);
      sp=factor(n);
      printf("largest prime factor is %ld",sp);
    
      printf("Time elapsed: %f\n", ((double)clock() - start) / CLOCKS_PER_SEC);
      getch();
     }