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

Tanmay ChakrabartyNice. 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.

SunilHi,

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

Daniel ScoccoPost 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?

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

AnommousIt 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 ðŸ™‚

suryanshthis code is giving following error

/* In function `main’:

:(.text+0xae): undefined reference to `fmod’

collect2: ld returned 1 exit status */

NOT WORKING