Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

I am trying to complete this challenge, which is to find the Find the largest Prime Factor of the number 600851475143.

My current solution is below:

static void Main(string[] args)
{
    const long targetNumber = 600851475143;
    var primeFactors = new List<long>();

    for (long i = 1; i <= targetNumber; i++)
    {
        if(PrimeFactor(targetNumber, i))
        {
            primeFactors.Add(i);
        }
    }

    var biggestPrimeFactor = primeFactors.Max();

    Console.WriteLine(biggestPrimeFactor);
    Console.ReadLine();
}

public static bool PrimeFactor(long number, long i)
{
    return number % i == 0;
}

My main problem is that this is taking ages to run, but it's also not very eloquent.

How can I improve on the above?

Thanks

share|improve this question
    
I'm trying to find the prime factor of a long in C#, not the prime number of an int in C++! –  JMK Mar 20 '12 at 19:58
1  
Alternative algorithms - stackoverflow.com/questions/23287/prime-factors –  Reddog Mar 20 '12 at 19:58
1  
You need to step back from the keyboard and think about the problem for a bit. There's a better way to find the largest prime factor. –  Kyralessa Mar 20 '12 at 20:06
7  
Your program is not correct, so don't try to make it faster. There's no point in writing a fast program that gets the wrong answer. Try it with a smaller number. What does your program say the largest prime factor is of 12? (Hint: the correct answer is 3.) Until you can write a program that gets the correct answer, don't try to speed it up. –  Eric Lippert Mar 20 '12 at 20:47
3  
@JMK: Your program as shown here in fact says 12, because it counts right up to the number itself, and that obviously divides itself with zero remainder. Some additional thoughts that might help you: (1) you only need to try primes up to the square root; and the number itself. The composite number 25, say, cannot have a largest prime factor bigger than 5, its square root. (Do you see why?) (2) If you find a prime factor, divide the big number by the prime factor. Why? Because then you just made the problem to solve smaller! –  Eric Lippert Mar 20 '12 at 23:15
show 2 more comments

migrated from stackoverflow.com Mar 20 '12 at 20:07

This question came from our site for professional and enthusiast programmers.

6 Answers

up vote 6 down vote accepted

I'd look into Max() function. Keeping track of the largest prime you have found so far might be better instead of using Max()?

Also how is the PrimeFactor function returning the largest prime factor? It looks like its only returning the divisor, not necessarily a prime number.

If your goal is to only return the largest prime factor, why don't you start counting from the targetNumber down to 0?

share|improve this answer
2  
Perhaps even start from targetNumber/2 or smaller? That should save a lot of useless checking. –  commando Mar 21 '12 at 0:24
    
yup, definitely agreed. –  c0d3Junk13 Mar 21 '12 at 1:16
    
@c0d3Junk13 Checking every number from 600851475143 in descending order sure sounds like an inefficient method to me. AFAIK the most efficient way to check if a number is prime is by using a prime sieve, which relies on knowing all previous prime numbers. –  Kirk Broadhurst Mar 21 '12 at 3:49
    
@KirkBroadhurst I saw your post. You're counting down from working number to 1. That is what I meant in my post as well. –  c0d3Junk13 Mar 21 '12 at 19:56
add comment

Note 2 things.

  1. There is at most 1 prime, bigger then sqrt(n)
  2. If p1 is prime factor, then either p1 is max prime factor, or you can divide by p1, without affecting largest factor. So all in all, it gives you code.

    static void Main(string[] args)
    
    {
        const long targetNumber = 600851475143;
        var primeFactors = new List<long>();
    
        for (long i = 1; i*i <= targetNumber; i++)
        {
            while(PrimeFactor(targetNumber, i))
            {
                primeFactors.Add(i);
                targetNumber /= i;
            }
        }
    
        primeFactors.Add(targetNumber);
        var biggestPrimeFactor = primeFactors.Max();
    
        Console.WriteLine(biggestPrimeFactor);
        Console.ReadLine();
    }
    
share|improve this answer
add comment

Gotta love Linq...

This would need to be tweaked to make it generic enough to use for any number (ie the Enumerable.Range only accepts ints) but it really shows off the power of Linq. This brings back the answer in .036 seconds on my machine.

void Main()
{
    const double targetNumber = 600851475143; 
    var biggestPrimeFactor = Enumerable.Range(2, Convert.ToInt32(Math.Sqrt(targetNumber)))
                                       .Reverse()
                                       .AsParallel()
                                       .Where(g => targetNumber % g == 0 && IsPrime(g))
                                       .FirstOrDefault();

    Console.WriteLine(biggestPrimeFactor); 
}

private static bool IsPrime(int number)
{
    for (int index = 2; index <= Math.Sqrt(number); index++)
        if (number % index == 0) return false;
    return true;
}
share|improve this answer
add comment

Easier solution:

static void Main(string[] args)
    {
        ulong n = 600851475143;
        ulong i = 1;
        ulong result;
        while (n != 1)
        {
            i++;
            how = 0;
            while (n % i == 0)
            {
                n /= i;
            }
        }
        result = i;
        Console.WriteLine(result);
    }
share|improve this answer
    
What's up with how = 0;? You don't define it, and you never use it. You also shouldn't need the variable result. This also doesn't take the 'easy' shortcut of iterating only to the square root - this setup isn't optimal for dealing with prime numbers. –  Clockwork-Muse Feb 4 '13 at 21:05
add comment

A few things about finding primes.

  1. Prebuild in the single digit primes 2, 3, 5, & 7 (and put into step 4 if used)
  2. The only numbers you need to check end with 1, 3, 7, or 9 (assuming you start after step 1)
  3. For a stage 1 increase in speed, use independent parallel checking by assigned range
  4. For a stage 2 increase, use a caching system to get the feed of the most up-to-date prime number list. When a prime number is found, feed it into the caching system.
  5. Bridge to pure C for the heavy lifting.

Item 2 = 60% reduction in numerical checks. Just use the base numbers and multiply them by 10 for each check. (17, 27, 37, 47, etc.)

Item 3 = utilization of multiple cores, possibly multiple separate computers. You can utilize .net's parallel.foreach() for ease of use.

Item 4 = in your example, you consider it a "list" of primes found. but each thread will need to lock/unlock access. It is better for each thread to pull in the list and use it as a primer for the next check if you are using parallel prime # checking.

Item 5 = removing as much .net and windows overhead as possible.

Since you are trying to get to the largest prime given the ceiling you provided, just check backwards for each 1, 3, 7, or 9. You'll probably find it within a few seconds-minutes.

share|improve this answer
add comment

Rather than checking every number to see which are divisors of your target, start by finding the prime factors of the target and then simply return the largest.

The fundamental rule of arithmetic tells us that the target has a single set of prime factors. We can infer that for the target T, T = p x V where p is the first prime factor found and V is the product of all remaining factors.

What this means is that you should loop through known prime numbers, dividing the target by each prime that is a factor. Keep doing this until the target is reduced to one - and the last prime number used as a divisor is the largest.

Thus

while workingTarget > 1

    if workingTarget % knownPrime = 0
        workingTarget = workingTarget / knownPrime
    else
        next knownPrime
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.