Solution to Project Euler 3

Problem 3 on Project Euler is another easy one. Here’s the description:

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

What is the largest prime factor of the number 600851475143 ?

A simple brute force approach, testing all factors of the number to see if they are prime and storing the largest one, solved it:

#include <stdio.h>
#include <math.h>

int isPrime(int n){
int i;
if (n%2==0)
return 0;
for (i=3;i<n/2;i+=2)
if (n%i==0)
return 0;
return 1;
}

int main(){
double n = 600851475143.0;
int i = 1;
while (i<50000){
if (isPrime(i))
if (fmod(n,(double)i)==0)
printf("%dn",i);
i++;
}
return 0;
}

6 thoughts on “Solution to Project Euler 3”

1. Tanmay Chakrabarty

Nice. I solved it the following way in vb.net

Imports System.Math
Dim t As Long = Val(TextBox1.Text) //= 600851475143
Dim s As Long = Math.Sqrt(t)
//None of the prime factors would be larger than the square-root of 600851475143.
//Thus the ans is residing from 2 to sqrt(600851475143) = 775146

Dim temp As Long
Dim got As Boolean = False
For i = s To 2 Step -1 //As we need the larger one, starting from top to 2
got = False
If (t Mod i = 0) Then //If this number is a factor of 600851475143
temp = Math.Sqrt(i)
//Then we have to find out if this number is a prime or not
//Thus we are again getting the square-root of this number

For j = 2 To temp Step 1
If Not (i Mod j = 0) Then
got = True
Else
got = False
Exit For //If not, no need to test anymore
End If
Next

If got = True Then //if its a prime, then this is the ans.
TextBox2.Text = i
Exit Sub
End If

End If

Next

**I know very soon you will find a way to view the program codes in your posts as they are in editors. I can’t find it. I mean in websites like geeksforgeeks.org they view the codes as like the codes are in editors (with colors, highlighted keywords etc). If you find it please share it, I also want to view my codes in that way.

2. Sunil

Hi,

This is a great site… really appreciate it.

In your method to check prime numbers, replace the logic for n/2 with sqrt(n). This will change the complexity of your code to log n

Sunil

3. Daniel Scocco Post author

@Sunil, yep I agree. Since this was a small problem I got lazy to type a couple of letters more to take the sqrt 🙂 .

Even with this change, though, I find that when you need to check primes in an efficient way the best way is to pre-generate a table with a sieve, and then do binary search. Agree?

4. Augusta

Great information! I have been previously trying to find something such as this for some time now. Many thanks!

5. Anommous

It can be done much easier:

long long input = 600851475143;
for(int i = 2; i < input; i++){
if(input % i == 0){
cout << input/i << endl;
break;
}
}

Does the trick 🙂

6. suryansh

this code is giving following error
/* In function `main’:
:(.text+0xae): undefined reference to `fmod’
collect2: ld returned 1 exit status */
NOT WORKING