代码之家 › 专栏 › 技术社区 › Tom Buck

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

factors initialization integer list c#

Tom Buck · 技术社区 · 8 年前

当我运行我的程序时,关键是我初始化了一个整数列表,然后它冻结了。我知道这是因为控制台。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;
        }
    }
}

3 回复 | 直到 8 年前

Peter Aylett 8 年前

iPrime将运行至少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”的最后一段代码建议您打算在更大的代码中使用它。如果是这种情况,最好预先计算哪些数字是素数,然后将它们存储在列表或哈希集中,以便快速重复使用。

MarcinJuraszek 8 年前

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

即使您等待它返回下一个循环运行 iPrime公司 对于2到3000亿之间的所有整数。这将需要更长的时间才能完成。它需要超过90万亿次的最内部循环迭代!

你想做什么还不是百分之百清楚,但你应该考虑一种不同的算法,因为无论你如何编写,这个算法都会运行得非常慢。

Tom Buck 8 年前

所以我在做欧拉计划的问题。在我做这件事的前一天,我成功地制作了一个dope素数查找算法,但我太懒了,没有把它放到第一篇文章中看到的素数分解问题中。在又一天拒绝查找答案、憎恨生活之后,我终于写了一个更好的程序。我现在可以在大约半秒钟内找到答案。可能会更干净,但它完成了我需要的#如此令人满意

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] + " ");
            }
        }

    }
}