Project Euler Question 3 Help

Question

I'm trying to work through Project Euler and I'm hitting a barrier on problem 03. I have an algorithm that works for smaller numbers, but problem 3 uses a very, very large number.

Problem 03: The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143?

Here is my solution in C# and it's been running for I think close to an hour. I'm not looking for an answer because I do actually want to solve this myself. Mainly just looking for some help.

    static void Main(string[] args) {
        const long n = 600851475143;
        //const long n = 13195;
        long count, half, largestPrime = 0;
        bool IsAPrime;

        half = n / 2;

        for (long i = half; i > 1 && largestPrime == 0; i--) {
             if (n % i == 0) { // these are factors of n
                count = 1;
                IsAPrime = true;
                while (++count < i && IsAPrime) {
                    if (i % count == 0) { // does a factor of n have a factor? (not prime)
                        IsAPrime = false;
                    }
                }
                if (IsAPrime) {
                    largestPrime = i;
                }
            }
        }

        Console.WriteLine("The largest prime factor is " + largestPrime.ToString() + ".");
        Console.ReadLine();
    }

Answer 1

For starters, instead of beginning your search at n / 2, start it at the square root of n. You'll get half of the factors, the other half being their complement.

eg:

n = 27
start at floor(sqrt(27)) = 5
is 5 a factor? no
is 4 a factor? no
is 3 a factor? yes. 27 / 3 = 9. 9 is also a factor.
is 2 a factor? no.
factors are 3 and 9.

Answer 2

long n = 600851475143L; //not even, so 2 wont be a factor
int factor = 3; 
while( n > 1)
{
    if(n % factor == 0)
    {
        n/=factor;
    }else
        factor += 2; //skip even numbrs
}
        print factor;

This should be quick enough...Notice, there's no need to check for prime...

Answer 3

Actually, for this case you don't need to check for primality, just remove the factors you find. Start with n == 2 and scan upwards. When evil-big-number % n == 0, divide evil-big-number by n and continue with smaller-evil-number. Stop when n >= sqrt(big-evil-number).

Should not take more than a few seconds on any modern machine.

Answer 4

Although the question asks for the largest prime factor, it doesn't necessarily mean you have to find that one first...

Answer 5

You need to reduce the amount of checking you are doing ... think about what numbers you need to test.

For a better approach read up on the Sieve of Erathosthenes ... it should get you pointed in the right direction.

Answer 6

As for the reason to accepted nicf's answer:

It is OK for the problem at Euler, but does not make this an efficient solution in the general case. Why would you try even numbers for factors?

• If n is even, shift left (divide by 2) until it is not anymore. If it is one then, 2 is the largest prime factor.
• If n is not even, you do not have to test even numbers.
• It is true that you can stop at sqrt(n).
• You only have to test primes for factors. It might be faster to test whether k divides n and then test it for primality though.
• You can optimize the upper limit on the fly when you find a factor.

This would lead to some code like this:

n = abs(number);
result = 1;
if (n mod 2 = 0) {
  result = 2;
  while (n mod 2 = 0) n /= 2;
}
for(i=3; i<sqrt(n); i+=2) {
  if (n mod i = 0) {
    result = i;
    while (n mod i = 0)  n /= i;
  }
}
return max(n,result)

There are some modulo tests that are superflous, as n can never be divided by 6 if all factors 2 and 3 have been removed. You could only allow primes for i.

Just as an example lets look at the result for 21:

21 is not even, so we go into the for loop with upper limit sqrt(21) (~4.6). We can then divide 21 by 3, therefore result = 3 and n = 21/3 = 7. We now only have to test up to sqrt(7). which is smaller then 3, so we are done with the for loop. We return the max of n and result, which is n = 7.

Answer 7

The way I did it was to search for primes (p), starting at 2 using the Sieve of Eratosthenes. This algorithm can find all the primes under 10 million in <2s on a decently fast machine.

For every prime you find, test divide it into the number you are testing against untill you can't do integer division anymore. (ie. check n % p == 0 and if true, then divide.)

Once n = 1, you're done. The last value of n that successfully divided is your answer. On a sidenote, you've also found all the prime factors of n on the way.

PS: As been noted before, you only need to search for primes between 2 <= n <= sqrt(p). This makes the Sieve of Eratosthenes a very fast and easy to implement algorithm for our purposes.

Answer 8

Once you find the answer, enter the following in your browser ;)

http://www.wolframalpha.com/input/?i=FactorInteger(600851475143)

Wofram Alpha is your friend

Answer 9

Using a recursive algorithm in Java runs less than a second ... think your algorithm through a bit as it includes some "brute-forcing" that can be eliminated. Also look at how your solution space can be reduced by intermediate calculations.

Answer 10

Easy peasy in C++:

#include <iostream>

using namespace std;


int main()
{
    unsigned long long int largefactor = 600851475143;
    for(int i = 2;;)
    {
        if (largefactor <= i)
            break;
        if (largefactor % i == 0)
        {
            largefactor = largefactor / i;
        }
        else
            i++;
    }

    cout << largefactor << endl;

    cin.get();
    return 0;
}

Answer 11

This solution on C++ took 3.7 ms on my Intel Quad Core i5 iMac (3.1 GHz)

#include <iostream>
#include <cmath>
#include <ctime>

using std::sqrt; using std::cin;
using std::cout; using std::endl;

long lpf(long n)
{
  long start = (sqrt(n) + 2 % 2);
  if(start % 2 == 0) start++;

  for(long i = start; i != 2; i -= 2)
    {
      if(n % i == 0) //then i is a factor of n                                                
        {
          long j = 2L;
          do {
              ++j;
             }
          while(i % j != 0 && j <= i);

          if(j == i) //then i is a prime number                                           
            return i;
        }
    }
}

int main()
{
  long n, ans;
  cout << "Please enter your number: ";
  cin >> n; //600851475143L                                                               

  time_t start, end;
  time(&start);
  int i;
  for(i = 0; i != 3000; ++i)
      ans = lpf(n);
  time(&end);

  cout << "The largest prime factor of your number is: " << ans << endl;
  cout << "Running time: " << 1000*difftime(end, start)/i << " ms." << endl;

  return 0;
}

Answer 12

All Project Euler's problems should take less then a minute; even an unoptimized recursive implementation in Python takes less then a second [0.09 secs (cpu 4.3GHz)].

from math import sqrt

def largest_primefactor(number):
    for divisor in range(2, int(sqrt(number) + 1.5)): # divisor <= sqrt(n)
        q, r = divmod(number, divisor)
        if r == 0:
            #assert(isprime(divisor))
            # recursion depth == number of prime factors,
            # e.g. 4 has two prime factors: {2,2}
            return largest_primefactor(q) 

    return number # number is a prime itself

Answer 13

you might want to see this: Is there a simple algorithm that can determine if X is prime, and not confuse a mere mortal programmer?

and I like lill mud's solution:

require "mathn.rb"
puts 600851475143.prime_division.last.first

I checked it here

Answer 14

Maybe it is considered cheating, but one possibility in haskell is to write (for the record I wrote the lines myself and haven't checked eulerproject threads);

import Data.Numbers.Primes
last (primeFactors 600851475143)

Answer 15

Try using the Miller-Rabin Primality Test to test for a number being prime. That should speed things up considerably.

Answer 16

Another approach is to get all primes up to n/2 first and then to check if the modulus is 0. An algorithm I use to get all the primes up to n can be found here.