# 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);
}
}
``````

### Footnote

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

ALGORITHM (Fundamental Theorem of Arithmetic)

Example:
The number 12.