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.

    Reply
  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

    Reply
  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?

    Reply
  4. 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 🙂

    Reply
  5. suryansh

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

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *