Whats the best way to find the largest prime factor of a number?

Question

I am new to programming and a friend of mine suggested that I should do the exercise on project Euler to get better in it. I encountered a problem on question 3:

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

Now here's my solution:

class Program
{
    static void Main(string[] args)
    {
        long number = 600851475143;
        bool prime = true;

        for (long i = 3; i <= number; i++)
        {
            for (long n = 2; n < i; n++)
            {

                if (i % n == 0)
                {
                    prime = false;
                    break;
                }
            }

            if (prime)
            {
                if (number % i == 0)
                {
                    Console.WriteLine(i);

                }

            }
            prime = true;

        }
        Console.ReadKey();
    }
}

Now, while i did get the correct answer (which is 6857) Ive found my method very inefficient. If you'll run my code you'll see that it'll still run after more than 2 minuets... My question is how can I write a more efficient/faster code for this?

First off you can cut the search space drastically, since a prime factor of any integer is always less than or equal to `sqrt(n)`. Where `n` is the number you are trying to factor — stackErr, Feb 18 '16 at 23:16
Possible duplicate of [Project Euler Question 3 Help](http://stackoverflow.com/questions/201374/project-euler-question-3-help) — Will Ness, Feb 18 '16 at 23:18
Seems like you should post the question [here](http://codereview.stackexchange.com/) — Eser, Feb 18 '16 at 23:18
You should be able to see others solutions now, since you solved it. Read what others have posted, see what optimizations they performed. Also, learn some mathematics around primes (it will be very useful in the long run). — stackErr, Feb 18 '16 at 23:20
BTW: if you can't find a whole number that can divide N till sqrt(N) then you can break the loop... — Eser, Feb 18 '16 at 23:21
the top-voted answers on the duplicate aren't good though, at all. Here's instead e.g. [my answer](http://stackoverflow.com/questions/15279278/finding-largest-prime-number-out-of-600851475143/15292911#15292911) with some pseudocode; there are many many others on SO. Just search for 600851475143. :) — Will Ness, Feb 18 '16 at 23:32
Possible duplicate of [Finding largest prime number out of 600851475143?](https://stackoverflow.com/questions/15279278/finding-largest-prime-number-out-of-600851475143) — rene, Dec 20 '17 at 21:39

Eric Lippert · Answer 1 · 2018-01-06T15:11:42.857

My question is how can I write a more efficient/faster code for this?

That's the wrong question. Or rather, it's a premature question.

The right questions to ask are:

Is my program correct?
Is my program well-organized?

Making an incorrect program fast gives you the ability to get wrong answers faster, which is not an improvement. Making a poorly organized program faster is really hard, so organize it well first.

Let's start by making a small but incredibly vital improvement to your program: we notice that "is this thing prime?" can be cleanly represented by a helper:

class Program
{
  static bool IsPrime(long i)
  {
    for (long n = 2; n < i; n++)
    {
      if (i % n == 0)
        return false;
    }
    return true;
  }

  static void Main(string[] args)
  {
    long number = 600851475143;
    for (long i = 3; i <= number; i++)
    {
      if (IsPrime(i))
        Console.WriteLine(i);
    }
    Console.ReadKey();
  }
}

Look what just happened there. Your program suddenly got much, much easier to understand. What does IsPrime do? It tells you if an integer is prime. What does the main loop does? It prints out all the primes between 3 and the number.

Now, start over. Is every part of the program correct? No. IsPrime returns true when given 1, but it is not normally considered a prime. Fix the bug. You want your helper methods to be reliable. Make sure your helper methods do exactly what they say on the tin. Write tests! Because you want to make sure that when you change these methods to make them faster, that you're not making them incorrect accidentally.

Now that we have both correct and well-organized we can start optimizing. Can you think of ways of making IsPrime faster? Sure:

We only have to check up to the square root of i. (Note that n * n <= i is faster than n <= Sqrt(i))
Once we've checked 2, we don't have to check 4, 6, 8, ...

Can you think of other ways to make it faster?

But the key is organize your program well. Once you have a well-organized program you can reason at a higher level, and you can find and eliminate slow pieces.

Just a minor suggestion. The type of parameter `i` should be `long`, not `int`. — Štěpán Beneš, Jan 06 '18 at 14:55

score 1 · Answer 2 · edited Aug 16 '16 at 20:38

I wrote a method that will give you all the prime factors, and the biggest one of them. My code is running, you can review it:

public void PrimeFactor1(long n)
{
    List<int> sList = new List<int>();
    long temp = 1;
    for (int i = 2; i <= n; i++)
    {
        if ((n % i) == 0)
        {
            temp = n / i;
            sList.Add(i);
            i = 1;
            n = temp;
        }     
    }
    string arr = string.Join(",", sList.ToArray());
    Console.Write(arr);
    Console.WriteLine(".");
    Console.WriteLine("The Biggest Prime number is: {0}", sList.Max());
}

rossum · Answer 3 · 2016-02-23T13:37:09.040

0

If you are going to be working on many Project Euler problems, then you will need a good implementation of the Sieve of Eratosthenes. Two of the useful methods for your Eratosthenes class are nextPrime(int p) and previousPrime(int p) which returns the next and next lowest prime numbers respectively.

ETA: Pseudocode redacted as incorrect. Sorry.

edited Feb 23 '16 at 13:37

answered Feb 20 '16 at 15:54

rossum

15,344
1
24
38

Whats the best way to find the largest prime factor of a number?

3 Answers3