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

本文关键字：最佳 方法 是什么 数字 | 更新日期: 2023-09-27 18:35:14

我是编程新手，我的一个朋友建议我应该在欧拉项目上做练习，以便在其中变得更好。我在问题 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 分钟后运行......我的问题是我如何为此编写更高效/更快的代码？

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

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

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

要问的正确问题是：

  • 我的程序正确吗？
  • 我的计划组织良好吗？

快速制作不正确的程序可以让您更快地获得错误的答案，这不是改进。 使一个组织得不好的程序更快真的很难，所以先把它组织好。

让我们从对程序进行一个小但非常重要的改进开始：我们注意到"这个东西是素数吗？"可以用一个助手干净地表示：

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 和数字之间的所有素数。

现在，重新开始。程序的每个部分是否正确？ 不。 当给定1时，IsPrime返回true，但它通常不被认为是素数。修复错误。 您希望帮助程序方法可靠。确保您的帮助程序方法完全按照它们在锡上所说的进行操作。 编写测试！因为您要确保在更改这些方法以使其更快时，不会意外地使它们不正确。

现在我们已经有了正确和组织良好的方法，我们可以开始优化了。 你能想到让IsPrime更快吗？ 确定：

  • 我们只需要检查 i的平方根 . （注意n * n <= i比n <= Sqrt(i)快）
    • 检查
  • 2 后，我们不必检查 4、6、8、...

你能想到其他方法来让它更快吗？

但关键是要组织好你的程序。一旦你有一个组织良好的程序，你就可以在更高的层次上进行推理，你可以找到并消除缓慢的部分。

我写了一个方法，可以给你所有的质因数，以及其中最大的一个。我的代码正在运行，您可以查看它：

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

如果你要处理许多欧拉项目问题，那么你将需要埃拉托色尼筛的良好实现。 埃拉托色尼类的两个有用方法是nextPrime(int p)和previousPrime(int p)，它们分别返回下一个和下一个最低素数。

ETA：伪代码被编辑为不正确。 不好意思。

相关文章：