c# 程序冻结在整数列表上

Question

当我运行我的程序时，它到达了我初始化整数列表并冻结的地步。我知道这是因为 Console.WriteLine();列表初始化后的方法不会出现在控制台上。当我运行它时，唯一的输出是"before list"。我错过了什么？我真的希望这不是显而易见的和令人尴尬的。

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

挂起的不是 List<T> 构造函数。它以 600_851_475_143 作为参数调用 IsPrime。循环运行是 3000 亿次迭代的一半。这需要时间。

即使您等待它 return 下一个循环运行s IsPrime 对于 2 和相同的 3000 亿之间的所有整数。这将需要更长的时间才能完成。它需要 inner-most 循环超过 90 万亿次迭代！

并不是 100% 清楚您要做什么，但您应该考虑一种不同的算法，因为无论您如何编码，这个算法都会运行非常慢。

Answer 2

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 中以便快速重复使用。

Answer 3

所以我在做欧拉计划的问题。在我做这件事的前一天，我设法做了一个很酷的求素数算法，但我懒得把它改成第一个 post 中看到的素因数分解问题。又是拒绝查找答案和厌恶生活的一天，终于写出了更好的程序。我现在可以在大约半秒内找到答案。可能会更干净，但它完成了我需要完成的工作。 #sosatisfying

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

namespace Euler._1_50
{
    class Challenge3_1
    {
        List<long> primes = new List<long>();
        List<bool> isPrime = new List<bool>();
        List<int> factors = new List<int>();

        long primeNums = 0;
        long bigNum = 600_851_475_143;
        int primeBnds = 1_000_000;

        public Challenge3_1()
        {
            genList();
            getPrimes();
            //listPrimes();
            factor();

            Console.WriteLine("final");
            listFactors();
        }


        //not currently being used
        private void genList()
        {
            for (int i = 0; i <= primeBnds; i++)
            {
                isPrime.Add(true);
            }
        }

        private void getPrimes()
        {
            isPrime[0] = false;
            isPrime[1] = false;

            for (int i = 2; i <= primeBnds; i++)
            {
                if (isPrime[i] == true)
                {
                    for (int j = i, index = 0; index <= primeBnds; index += j)
                    {
                        if (j < index)
                        {
                            isPrime[index] = false;
                        }
                    }
                }
            }
        }

        private void factor()
        {
            long temp = bigNum;

            for (int i = 2; i <= primeBnds;)
            {
                if (isPrime[i] == true && temp % i == 0)
                {
                    temp = temp / i;
                    factors.Add(i);
                    Console.WriteLine(i);
                }

                if (temp % i != 0)
                {
                    i++;
                }

                //if (factors.Capacity != 0) listFactors();
            }

        }

        private void listPrimes()
        {
            for (int i = 0; i <= primeBnds; i++)
            {
                if (isPrime[i] == true)
                {
                    Console.WriteLine(++primeNums + " " + i);
                }
            }
        }

        private void listFactors()
        {
            for (int i = 0; i < factors.Capacity; i++)
            {
                Console.Write(factors[i] + " ");
            }
        }

    }
}

c# 程序冻结在整数列表上

c# program freezes on list of integers

c#

integer

initialization

list

factors