# Project Euler – Problem 3

I am sorry, I haven’t posted anything for a while. I have been busy moving, and is currently without an Internet connection. However I couldn’t keep away any more.

Problem 3 in Project Euler reads:

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

What is the largest prime factor of the number 600851475143 ?

I used two different approaches for this, and lets get right to them.

## Brute forcing

Like the first two problems, my first question is; “Can it be brute forced”, and the answer to that is “not really”. I tried with a bang on approach without using any mathematical short cuts. The code would look something like

```const long numm = 600851475143;
long largestFact = 0;

for (long i = 2; i < numm; i++) {
if (numm % i == 0) { // It is a divisor
bool isPrime = true;
for (long j = 2; j < i; j++) {
if (i % j == 0) {
isPrime = false;
break;
}
}
if (isPrime) {
largestFact = i;
}
}
}
```

The approach is to check all numbers less than the number we are checking. If the number is a factor (checked by the modulo operator) we check all numbers less than the found factor, to check that there are no factors to that number.

For many people this is an obviously slow method, and I agree. But I think it is fun to take the head on approach. I don’t have the timing for this approach, since I lost patience and stopped it.

In order to brute force the problem, we need to use a small trick. Any factor less than the square root of the number we check, will have corresponding factor larger than the square root of the number. So we only need to check up to the square root of the number, and then we can deduct the remaining factors.

Example:
The number 24, has the factors 2,3, 4, 6, 8 and 12.
The square root of 24 is approximately 4.8, so we are save to check all numbers up to and including 4.

This gives us 2,3 and 4 as factors. The rest can be deducted as:
24/2 = 12
24/3 = 8
24/4 = 6

So lets code something that utilises the fact that we only need to check all numbers up to the square root when looking for factors.

```const long numm = 600851475143;
long largestFact = 0;
long[] factors = new long;

for (long i = 2; i * i < numm; i++) {
if (numm % i == 0) { // It is a divisor
factors = i;
factors = numm / i;

for (int k = 0; k < 2; k++) {
bool isPrime = true;
for (long j = 2; j * j <  factors[k]; j++) {
if (factors[k] % j == 0) {
isPrime = false;
break;
}
}
if (isPrime && factors[k] > largestFact) {
largestFact = factors[k];
}
}
}
}
```

The first change is that I check if i*i is less than the number, which is equivalent to check up to the square root. So we need a lot fewer iterations. I have created an array to to store the found and the corresponding factor. I then check each of them to check if they are primes.

The result of the code is

```The largest primefactor of 600851475143 is: 6857
Solution took 15,625 ms
```

which is quite an improvement just by using this little fact.

## Alternative Solution

As I started the post by saying, there is an alternative, and faster solution than brute forcing. However, it turned out to work well enough for this problem.

We can use the Fundamental Theorem of Arithmetic which states:
Any integer greater than 1 is either a prime number, or can be written as a unique product of prime numbers (ignoring the order).

Example:
The number 12.
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.

A more elaborate explanation can be found here

We make a logical short cut here and realise that we don’t need to find all prime numbers first, we can “just” enumerate through all numbers until we have a complete factorization if we start from below, since all non-prime factors will already be factorized in primes, as a consequence of the proof given in the link to the theorem. Lets write some code shall we.

```const long numm = 600851475143;
long newnumm = numm;
long largestFact = 0;

int counter = 2;
while (counter * counter <= newnumm) {
if (newnumm % counter == 0) {
newnumm = newnumm / counter;
largestFact = counter;
} else {
counter++;
}
}
if (newnumm > largestFact) { // the remainder is a prime number
largestFact = newnumm;
}
```

We start with 2, and check how many times that number is divisible with the remainder we have. Once 2 is not a divisor to the remainder we increase the counter by one and check 3, 4 and so on. If 4 was a factor to the original number, 2 will be a factor at least twice as well. And then we can go on, until the counter is larger than the square root of the remainder.

If the remainder is different from one, then the remainder is also a prime factor. However I only need to check if it is larger than the largest factor found, to see if it is interesting. This code executes below measurable time on my computer.

```The largest primefactor of 600851475143 is: 6857
Solution took 0 ms
```

Actually we can improve it a bit, by changing

```counter++;
```

with

```counter = (counter == 2) ? 3 : counter + 2;
```

Which is a compressed if construct. If the counter is two, we increase it to 3, otherwise we increase it by 2 so we only check 2 and the odd numbers. It doesn’t really make much of a difference for the execution speed of this problem.

I hope that these notes has taught you something, and triggered your curiosity to explore further. ### Posted by Kristian Abdullah

nice use of Fundamental Theorem of Arithmetic msdn

very very good.thank you.i am one of your site’s fans. Kristian

Thank you Hi Kristian, this is awesome! 🙂 I have one problem though..

The fact that we only need to check all numbers up to the square root when looking for factors of a number doesn’t seem to apply to the number 28. Its prime factorization is 2, 2, 7. Now the square root of 28 is around 5.29. This means I can only get the 2’s but not the 7 since the algorithm will only check numbers up to 6 (its square root rounded up).

For higher numbers, the algorithm applies really well though.

Thoughts? Kristian

This is a long time ago, so I have probably become somewhat wiser since I wrote it.
You are right in your argumentation is correct. You can indeed have a prime factor which is larger than the square root. In fact there is infinitely many numbers where that is true.

However, what I think you are missing is the fact that once you have factored out all prime factors below the square root the remainder will also be a prime factor.

And we can actually prove that. Suppose we have an integer m = n^2. Where n is a real number. And suppose that we have two prime factors to n called a and b, such that a,b > n

Then we can write a = n + c and b = n + d where c and d are strictly positive numbers as well. Since the number is equal to the product of all the prime factors we get that m >= a*b (the greater than comes from the fact that there might be more prime factors.

We can write m >= a*b = (n+c)*(n+d) = n^2 + n*c + n*d + c*d = m + k
where k = n*c + n*d + c*d > 0. This is a contradiction. And therefore we can conclude that we can have a maximum one prime factor larger than the square root.

So to conclude again. The algorithm factors out all the prime factors below the the square root. If there is a quotient larger than 1 once this is done, then that quotient will be a prime factor as well. That really cleared it up Kristian. So it is possible to have a maximum of one prime factor larger than the square root. And to find this prime factor (hoping it’s greater than 1), we simply divide the number by all the prime factors that were found less than the square root. Thank you! Akshat

I hv taken a bit diff approach-
My JS code –
function largestprime(n) {
var i = 2;
while(i <= n) {
if (n % i == 0) {
n /= i;
}
else {
i++;
}
}
console.log(i)
}
var a = 600851475143 ; Ankur Sao

What do you think about using a sieve first,to setup an array of primes and than using brute force to check for the largest prime factor .
Will it enhance the performance of the program significantly or will not be helpful at all ? Kristian

When I wrote this code, I didn’t know of sieves. So it is quite possible it would speed things up. I can only encourage you to try an implementation with sieves. Keerthi

i happened to solve the problem and look in the discussion, found none of them are using the prime factorization (i used the principle to solve).
Cheers for explaining it in detail.

My solution in java

```
public static boolean isPrime(long n) {
if (n &lt; 2) return false;
if (n == 2 || n == 3) return true;
if (n % 2 == 0 || n % 3 == 0) return false;
long sqrtN = (long) Math.sqrt(n) + 1;
for (long i = 6L; i &lt;= sqrtN; i += 6) {
if (n % (i - 1) == 0 || n % (i + 1) == 0) return false;
}
return true;
}
public static long largestPrimeFactor(long inNumber) {
if(isPrime(inNumber))
return inNumber; //if the number itself is prime, don't bother computing
int upperLimit = (int) Math.sqrt(inNumber);
int i = 2;
int divisor = 1;
while(i<upperLimit){
if(inNumber%i == 0){
if(isPrime(i)){
divisor *=i;
if(isPrime(inNumber/divisor)){
return inNumber/divisor;
}
}
}
i+=2;
if(i==2)
--i;
}
return 1;
}
```

[…] happen to read mathblog.dk after writing this, Kristian explained all solutions much clear over […] Ghale

Your Alternative solution does not work for numbers like 500 and 50. I think your while condition should look like

(counter * counter < newnumm || counter * counter == newnumm)

to be full proof. Kristian

You are right that is updated now. Though I think the easy way is to write it

(counter * counter <= newnumm) annie

I have done its very easy, and optimised solution. Check this out here @ http://crispylogs.com/project-euler-problem-3-solution/ harry

For the alternative solution you could simplify it slightly by changing your while loop to stop when your newnumm = 1. This is essentially the same as when counter exceeds the newnumm but it allows you to collect the last prime factor as counter. In your solution the newnumm ends up being the largest prime at loop end.

Here is my python solution that returns a list of all the prime factors of any number. Runs in below measurable time for the Euler problem.

```def getPrimeFactors(target) :
factors = []

counter = 2
while (target &gt; 1):
if target % counter == 0 :
target = target / counter
factors.append(counter)
else :
counter += 1 if counter == 2 else 2
return factors

target = 600851475143
factors = getPrimeFactors(target)

print &quot;The largest prime factor of &quot; + str(target) + &quot; is &quot; + str(max(factors))
print factors
``` mrb

Hi,

I have created this Matlab code. It uses the primes function of matlab, but you can ofcourse also create your own prime numbers within in a short period of time.

Given the slowness of Matlab, it is actually really fast, about 0.008s.

``` number = 600851475143; prime_vector = primes(10000)'; prime_factors = 1;```

``` ```

```while number ~= 1 for i = 1 : size(prime_vector,1) if mod(number,prime_vector(i,1)) == 0 prime_factors(end+1,1) = prime_vector(i,1); number = number/prime_vector(i,1); break; end end end disp(prime_factors(end,1)) ``` Haakon

I used a slightly different algorithm.

What I did was to use a simple prime-generator (I haven’t bothered to optimize it for speed, it doesn’t even use the square root trick, it instead just tries to factorize possible prime numbers against previously generated ones, saving time that way.) and then in pseudo code:

``` number = 600_851_475_143```

``` largestPossibleFactor = primeGenerator.generateNextPrime(); while(number != 1) { if number is evenly dividable by largestPossibleFactor { number /= largestPossibleFactor; } else { largestPossibleFactor = primeGenerator.generateNextPrime(); } } ```

```return largestPossibleFactor; } ```

The entire algorithm is pretty straightforward. If a number is a factor, we divide by this number until we get a number that isn’t a factor. Because of the properties of multiplication/factorization this works.

Since we don’t want to divide by every single number ever, we just divide by prime numbers.
It might be faster to divide out 2 first, and then just try every odd number, but I felt that it would be a much uglier solution, since what we care about is the prime factors, not the factors as such. blach

#include

int i, number=2;

int primeFactors(int x, int prime){

if(x==1)
return prime;
if(prime==2 && x%prime==0)
return primeFactors(x/prime,prime);
else if(prime==2 && x%prime!=0)
prime=3;

if(x%prime==0)
return primeFactors(x/prime,prime);
else
return primeFactors(x,prime+2);

}

int isPrime(int number){
int i, counter=2;
for(i=2; i<number; i++){
if(number%i==0)
counter++;
}

if(counter==2)
return 1;
return 0;
}
int main(){
int n;
scanf("%d",&n);
int final=primeFactors(n,number);
printf("%d\n",final );

}

I works , but when I put the number that is needed there's a segmentation fault. Does anybody knows where is the problem?
thanks! Resham

I came up with following solution in java. Does it have any flaw?

public static void main(String args[])
{
long num = 600851475143L;
for(long i = 2 ; i <= Math.sqrt(num); i++)
{
while( num % i == 0)
{
num = num / i;
}
}
System.out.println("Largest Prime factor : "+ num);
} Rosi

Hej Kristian,

I just wanted to give you my 2 cents.

First I have been fighting to Sieves for like 2 days. And I found out that Eratosthenes sieve is not good enough to work with this number. Maybe Euler Sieve? I do not know. I do not have more time to spend on it. I personally did not manage to make the sieve work. I can post my code if you want to.

I solved this problem with similar solution to your ‘brute force’ but with out the array.

Essentially

for (i*i < number) loop
if statement number mod i
I accept the the number is prime = true
for (j*j < i)
if statement to check again for mod of i vs j
prime = false
largestnumber = (int) i;

it gets it right in 25ms your solution on my machine takes 49ms.

I can post this code as well if you want.

Best regards
Rosi Dan

I used this as my C# code (Before looking here. I think it uses the fundimental theorem of arithmetic but isn’t as efficient as yours.)
``` long div = 2; long num = 600851475143;```

``` while (div != num) { if ((num % div) == 0) { num /= div; Console.WriteLine(div); for (int i = 2; i < div; i++) { Console.WriteLine(num); } } else { div += 1; } ```

``` } ``` CJS

int main(){
long long num=600851475143,a=2;
while(a<num){
if(num%a==0){
num=num/a;
}else{
a++;
}
}
cout<<num;
} Jean-Marie Hachey

Problem Euler 3 …
Another solution in C#

http://rextester.com/GSNP67206 RStudioCoolio

library(numbers)

primeFactors(600851475143)
 71 839 1471 6857 Enea Mapelli

Alternative method fail with 60085647517 which is a product of 2 prime number. Here’s the output,with steps:
(largestFact,newnumm)
(7, 8583663931)
(-1, -8583663931)
Highest prime factor of 60085647517 = -1
Elapsed time: 35.0321 s
Solved using long instead of int also for cont. sanchi garg

It also won’t work for 39.
The largest prime factor of 39 will be 13 but the square root of 39 is 6.2449979984. It won’t give 13 as largest prime factor. Logique_Viper

#include
#include <bits/stdc++.h>
using namespace std;
int main(){
unsigned long long int mxN = 600851475143;
for (unsigned long int fact = 2;fact*fact<=mxN;++fact){
while (mxN%fact == 0 and mxN != fact){
mxN = mxN/fact;
}
}
cout<<mxN<<endl;
}