Problem 3: Largest prime factor

*Difficulty: Easy

Problem:

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

How to solve:

There are many possible approaches,Pollard’s rho algorithmShanks’ square forms factorizationLenstra elliptic curve factorizationQuadratic sieveGeneral number field sieve to name a few. 

My approach is using sieve Eratosthenes algorithm to create a prime numbers dictionary. As you may notice, we don’t need to calculate the prime numbers bigger than the square root of 600851475143 (google for more details) , which is 775146 . So the largest prime number in the dictionary will never exceed 800000 (I want to make sure everything is in the dictionary). We loop from 2 to 775146, check if that number is divisible by 600851475143 and is a prime number, if it is, check if it is bigger than max (which is initialized by -Infinity) . If the conditions are true, then assign i to max.

(Or we can loop from 775146 to 2 , if the first number that divisible by 600851475143 is a prime number, then it has to be the biggest prime factor. This will save some assignment statements, but the amount of time it takes will be relatively equal with the above method)

Implementation (Java):

import java.math.BigDecimal;

import java.util.Arrays;

public class Prob3 {

        private static boolean[] sieveEratosthenes;

        privatestaticfinalintSIZE = 800000;

        public static void main(String[] args) {

        //using sieve Eratosthenes algorithm to create a prime numbers dictionary

        long cur = System.currentTimeMillis();

        sieveEratosthenes= new boolean[SIZE];

        Arrays.fill(sieveEratosthenes, true);

        for(int i = 2; i < sieveEratosthenes.length; ++i ){

                if(sieveEratosthenes[i]) {

                        for(int j = 2*i; j < sieveEratosthenes.length; j+=i)

                        sieveEratosthenes[j] = false;

                }

         }

         int limit = (int)Math.sqrt(600851475143l);

         long number = 600851475143l;

         for(int i = limit; i >=2 ; i) {

                 if(number%i==0 && isPrime(i)){

                          System.out.println(i);

                          System.out.println(“Took “ + (System.currentTimeMillis()cur) + “ms”);

                         break;

                 }

        }

        /*

         int max = Integer.MIN_VALUE;

         for(int i = limit; i >=2 ; –i) {

                    if(number%i==0 && isPrime(i)){

                               if(i > max)

                                           max = i;

                   }

          }

        System.out.println(max);

        System.out.println(“Took ” + (System.currentTimeMillis()-cur) + “ms“);

        */

         }

          privatestaticbooleanisPrime(int n) {

                      return sieveEratosthenes[n];

          }

}
Solution took <50 ms

Advertisements