什么是找到数字最大素数的最佳方法？

Question

我是编程的新手,我的一个朋友建议我应该对Euler项目进行练习以使其更好.我在问题3上遇到了问题:

"13195的主要因素是5,7,13和29. 600851475143中最大的主要因素是什么？"

现在这是我的解决方案:

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

现在,虽然我确实得到了正确的答案(这是6857),但我发现我的方法非常低效.如果您将运行我的代码,您将看到它仍将在超过2分钟之后运行...我的问题是如何为此编写更高效/更快的代码？

Answer 1

我的问题是如何为此编写更高效/更快的代码？

这是错误的问题.或者更确切地说,这是一个不成熟的问题.

要问的正确问题是:

• 我的程序是否正确？
• 我的计划组织得很​​好吗？

快速制作错误的程序使您能够更快地得到错误的答案,这不是一种改进. 制作一个组织不良的程序真的很难,所以先组织好.

让我们首先对你的程序做一个小但非常重要的改进:我们注意到"这件事情是不是很重要？" 可以由助手干净地代表:

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

看看那里发生了什么. 你的程序突然变得更容易理解.IsPrime做什么？它会告诉您整数是否为素数.主循环有什么作用？它打印出3和数字之间的所有素数.

现在,重新开始.该计划的每个部分都是正确的吗？给定时IsPrime返回 编号 ,但通常不认为是素数.修复错误.您希望辅助方法可靠.确保你的辅助方法完全按照他们对锡的说法进行.写测试!因为你想确保当你改变这些方法以使它们更快时,你不会意外地使它们变得不正确.true1

现在我们既有正确又有条理,我们可以开始优化.你能想到让IsPrime更快的方法吗？当然:

• 我们只需要检查平方根i.(注意n * n <= i比快n <= Sqrt(i))
• 一旦我们检查了2,我们就不必检查4,6,8 ......

你能想到其他方法来加快速度吗？

但关键是要很好地组织你的计划.一旦你有一个组织良好的程序,你可以在更高的层次上推理,你可以找到并消除缓慢的部分.