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

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?

Answer 1

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.