Reputation: 5692

Project Euler Question 3 Help

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();
    }

Upvotes: 17

Answers (16)

stian

Reputation: 1987

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)

Upvotes: -1

Dangrr888

Reputation: 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;
}

Upvotes: 1

Dr. belisarius

Reputation: 61026

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

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

Wofram Alpha is your friend

Upvotes: 2

Deepak

Reputation: 11

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

Upvotes: 1

st0le

Reputation: 33545

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

Upvotes: 10

pageman

Reputation: 3022

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

Upvotes: 0

Matthew Scharley

Reputation: 132284

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.

Upvotes: 2

Ralph M. Rickenbach

Reputation: 13183

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.

Upvotes: 3

nickf

Reputation: 546085

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.

Upvotes: 15

jfs

Reputation: 414345

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

Upvotes: 0

Bill Barksdale

Reputation: 2456

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

Upvotes: 10

Steve Moyer

Reputation: 5733

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.

Upvotes: 1

AquilaX

Reputation: 1278

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.

Upvotes: -1

JesperE

Reputation: 64414

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.

Upvotes: 10