views:

2274

answers:

14

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();
    }
+6  A: 

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.
nickf
I changed my starting point to this: startAt = (long)Math.Floor(Math.Sqrt(n));and that gave me an immediate answer. Thanks!
rodey
This method finds the factor of the number, but it will include both prime and not prime numbers. For example 9 is not prime.
Jim C
Once you find 3, you set n = n / 3 = 9 and repeat from there.
Just Some Guy
@Jim: Yep, that would be the first part of the question. To find the prime factors, you also gotta find the factors. Though, I guess you could do it the other way around and find the primes first. @JSG: Why would you do that?
nickf
@nickf: Starting at floor(sqrt(n-1)) is not safe e.g. 25: floor(sqrt(24)) = 4, is 4 a factor? no, 3? no, 2? no. Thus 5 is missed.
J.F. Sebastian
oh - that was a typo sorry. It's not supposed to be sqrt(n - 1). I've fixed that now.
nickf
+5  A: 

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.

Rob Walker
I originally looked into this but I think I had a couple problems. I was trying to generate a list from 1...n and I was running out of memory. I do need to implement this though because I am sure it is going to come in handy in these problems.
rodey
When N is that high you would need to do things in slices: use an array to compute the primes 1 ... 1,000,000 then use these and rerun the algorithm between 1,000,000 and 2,000,000 .. etc. This will keep the memory to a fixed bound.
Rob Walker
Or do it lazily; for example using a generative iterator.
TraumaPony
A: 

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

Nicholas Mancuso
And is massively overkill for this sort of thing. If OP can't work out how do this quickly with simple tests I don't fancy his chances of getting Miller-Rabin working easily.
Ian G
true, but a lot of the PE problems involve primes. So writing a subprogram once to handle determining primality will be helpful in the long run.
Nicholas Mancuso
+9  A: 

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

Bill Barksdale
I agree, finding the smaller prime factors will be easier and reduce the problem space.
PhirePhly
+3  A: 

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.

JesperE
That exactly is the approach I too took to solve this one. I've given a description of the algorithm and some code (in perl) in my blog (http://thetaoishere.blogspot.com/2008/05/largest-prime-factor-of-number.html). My runtime was only around 14 ms or so (in perl)...
sundar
thanks - i realise this post is old but still! i suck at maths but enjoy programming and hate being beaten by problems, if it wasnt for this post i would have been going for another 3 months !!!
simion
This is the beauty of SO being optimized to allow people to find good answers to old questions.
JesperE
+2  A: 

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.

Ralph Rickenbach
A: 

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.

AquilaX
sqrt(n) is better ;)
SemiColon
A: 

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.

Steve Moyer
+2  A: 

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.

Matthew Scharley
A: 

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
J.F. Sebastian
A: 

you might want to see this: http://stackoverflow.com/questions/188425/project-euler-problem

and I like lill mud's solution:

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

I checked it here

pageman
A: 
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...

st0le
+1  A: 

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

     http://www.wolframalpha.com/input/?i=FactorInteger[600851475143]

Wofram Alpha is your friend

belisarius
A: 

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