c# - 你能帮我优化这段代码来查找数字的因子吗？我正在温习数学编程

Question

我从来没有真正关心过数学编程，但今天我决定尝试一下。

这是我的代码，它按预期工作:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Windows;
using System.Windows.Controls;
using System.Windows.Data;
using System.Windows.Documents;
using System.Windows.Input;
using System.Windows.Media;
using System.Windows.Media.Imaging;
using System.Windows.Navigation;
using System.Windows.Shapes;

namespace PrimeFactorization
{
    /// <summary>
    /// Interaction logic for MainWindow.xaml
    /// </summary>
    public partial class MainWindow : Window
    {
        public MainWindow()
        {
            InitializeComponent();
        }

        private void btnSubmit_Click(object sender, RoutedEventArgs e)
        {
            List<int> primeFactors = FindPrimeFactors(Convert.ToInt32(txtNumber.Text));
            primeFactors.Sort();
            for (int i = 0; i < primeFactors.Count; i++)
            {
                listBoxFoundNumbers.Items.Add(primeFactors[i]);
            }            
        }

        private List<int> FindPrimeFactors(int number)
        {
            List<int> factors = new List<int>();
            factors.Add(1);
            factors.Add(number);

            for (int i = 2; i < number; i++)
            {

                if (number % i == 0)
                {
                    int holder = number / i;
                    //If the number is in the list, don't add it again.
                    if (!factors.Contains(i))
                    {
                        factors.Add(i);
                    }
                    //If the number is in the list, don't add it again.
                    if (!factors.Contains(holder))
                    {
                        factors.Add(holder);
                    }
                }            
            }

            return factors;
        }
    }
}

我在代码中看到的唯一问题是它会迭代到痛苦的结局，即使肯定不会有任何因素。

例如，假设我用 35 编写。我的循环将上升到 35 并检查 24,25,26,27...等。不太好。

你有什么建议？

Answer 1

您可以做的一件事是避免检查 2 之后的偶数，因为它们永远不会是质数。

因此，检查 2，然后按如下方式声明循环:

for (int i = 3; i < number; i+=2)

回复:停在 sqrt(n) - 这是确定给定数字是否为素数的有效技术，因为任何 n划分 x哪里x > sqrt(n)也分为n/x这必然小于 sqrt(n) 。但一个数的质因数可能大于其平方根(例如，1002 = 2 * 3 * 167)。

也就是说，您可以实现某种递归解决方案，其中对于所有素数 p的n这样p < sqrt(n) ，您还可以计算 n / p 的素因子。我的直觉是，这通常会减少算法的运行时间，但对于 n 的小值可能会增加它。 .

编辑:如果您有兴趣了解更复杂的技术，请参阅 Integer Factorization 上的维基百科页面。各种算法的链接。