Project Euler Problem 3 Solution

First posted on 09/09/2012

Question

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

What is the largest prime factor of the number 600851475143 ?

Solution in Java

public class PrimeFactor {
	public static void main(String[] args){
		long num = 600851475143L; // Big number
		long newnum = num;
		long largestFactor = 0;
		
		int counter = 2;
		while(counter * counter < newnum){ // Sqrt? i don't get this part
			if(newnum % counter == 0){ // Each newnum will be checked if divisible by counter
				newnum = newnum / counter; // See ALGORITHM below
				largestFactor = counter; // Largest factor now is the counter
			} else { // If it is not divisible then counter will be increased
				
				// if (counter == 2), true:false
				counter = (counter == 2) ? 3 : counter + 2;
			}
		}
		
		if(newnum > largestFactor){
			largestFactor = newnum;
		}
		
		System.out.println(largestFactor);
	}
}

Answer: 6857

Footnote

Copied shamelessly from http://www.mathblog.dk/project-euler-problem-3/

ALGORITHM (Fundamental Theorem of Arithmetic)

Example:
The number 12.
We start with the smallest prime number (2).
12/2 = 6, which means that 2 is a prime factor to 12.
We try again to divide the remainder with 2 again:
6/2 = 3. Three is a prime number as well, so we now have the complete factorization which is
Prime factorization of 12 is 2,2,3 and we can check that 223=12.

Prime number =/= Prime factor

Prime number is only divisible by 1 or itself
Prime factor is the factors of how to get a NON-prime number

Show Comments

Get the latest posts delivered right to your inbox.