C# 程序卡住在整数列表上

Question

当我运行我的程序时，它达到了我初始化一个整数列表并且它卡住的地步。我知道这一点是因为 Console.WriteLine();列表初始化后的方法不会出现在控制台上。当我运行它时，唯一的输出是“列表之前”。我缺少什么？我真的希望这不会太明显和令人尴尬。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Euler._1_50
{
    class Challenge3
    {
        public Challenge3()
        {
            Console.WriteLine("before list");

            long num = 600_851_475_143;
            long high = 0;
            long length = 0;
            List<int> factr = new List<int>();

            Console.WriteLine(IsPrime(num));
            Console.WriteLine("after list");

            for (long i = 2; i <= num / 2; i++)
            {
                if (IsPrime(i) && num / i == 0)
                {
                    num = num / i;
                    factr.Add((int)i);
                    length++;
                }
            }

            for (long i = 0; i <= length; i++)
            {
                if (i > high) high = i;
            }

            Console.WriteLine(high);

        }

        private bool IsPrime(long i)
        {
            bool isPrime = false;

            for (long j = 2; j <= i/2; j++)
            {
                if (i % j == 0) isPrime = false;
                else isPrime = true;
            }
            return isPrime;
        }
    }
}

Answer 1

IsPrime 将运行至少 3000 亿次迭代，这就是它锁定的原因。

整数的质因数永远不会大于该整数的平方根。

此外，一旦确定该数字是质数，就无需继续检查。

因此请考虑将测试循环更改为:

private bool IsPrime(long i)
{
    long upper = (long)Math.Sqrt(i);
    for (long j = 2; j <= upper; j++)
    {
        if (i % j == 0)
           return false;
    }
    return true;
}

最后，关于“high”的最后一段代码表明您打算在更大的代码段中使用它。如果是这种情况，您最好预先计算哪些数字是素数一次并将它们存储在 List 或 HashSet 中以便快速重复使用。