项目Euler #3卡住

Question

我真的不希望它变成这样，当然体育的重点是我应该自己去解决问题。

前两个我用了不到一个小时，不幸的是我被问题3完全困住了。现在我尝试了传统的试除法，当然这太慢了，我试着用平方(N)除以优化除法，但是要得到600,851,475,143这个最高的素数还是太慢了。

现在我甚至试着用Eratosthenes的筛子来做这件事，我不得不承认我很难理解，但它仍然没有削减它。首先，“标记”数的数量会导致一个异常，因为当你试图生成所有的素数高达600,851,475,143时，条目的数量会变得巨大。

我被困住了，坦白地说，我现在正处在一个我开始对此感到烦恼的地方。

这是我的密码：

class Program
    {
        // The prime factors of 13195 are 5, 7, 13 and 29.
        // What is the largest prime factor of the number 600851475143 ?
        static void Main(string[] args)
        {

            Console.WriteLine(GetHighestPrimeFactor(600851475143).ToString());
            Console.ReadKey();
        }

        static List<long> GeneratePrimeNumbers(long n)
        {
            // Let's use the Sieve of Eratosthenes for this
            var markedNumbers = new List<long>();
            var primes = new List<long>();

            for (long i = n / 2; i < n; i++)
            {
                // If this is false then this is a prime number, add it to the list of primes
                if (!markedNumbers.Contains(i)) 
                {
                    primes.Add(i);

                    for (long j = i; j <= n; j+= i)
                    {
                        markedNumbers.Add(j);
                    }
                }
            }

            return primes;
        }

        static long GetHighestPrimeFactor(long n)
        {
            var primes = GeneratePrimeNumbers(n);

            // Loop backwards and return when we hit the first prime number
            for (long i = n / 2; i > 1; i--)
            {
                if (n % i == 0)
                {
                    if (primes.Contains(i))
                    {
                        return i;
                    }
                }
            }

            //Code should not reach this point of execution
            return -1;
        }

Answer 1

当然，体育课的重点是我应该自己解决问题。

好的，这里有一些提示，而不是答案。

我试着通过除以sqrt(n)来优化除法

我看不出这有什么用。假设你试图找出74这个最大的素因子。74的平方根是8点左右。把74除以8是有什么帮助的？

现在我甚至试着用埃拉托斯提尼的筛子来做这个

筛子是用来找素数的。你的理论是，你要找出所有的素数，直到想要的数，然后找出除以这个数的最大数吗？

对于一个庞大的数字来说，这在计算上太昂贵了。

以下是你的提示：

• 如果一个数n>0是素数，那么它就是它自己的最大素数因子。
• 如果一个数n>0是复合的，那么它就是x*y，其中两者都不是1。
• 这两个数字中有一个小于或等于n的平方根。
• N的最大素数等于x的最大素数或y的最大素数。

如果你不明白为什么其中一个事实是真实的，停止思考，直到你做。在接下来的几个欧拉问题上，你不会有任何进展，除非你已经冷静下来了。

现在，有了这些提示，您应该能够将问题分解为一系列较小的问题。

Answer 2

我自己读过关于Eratosthenes的筛子，但是我对素因式分解的技巧不太了解。我不确定从生成所有已知素数的列表开始，这是一个很好的技巧。我并不是说这很糟糕，我只是怀疑也许更实用的技术不会采用这种方法，因为它会有巨大的空间需求。

因此，我将建议对素数列表中的内存使用问题进行一些修正。

例如，我会将GeneratePrimeNumbers的结果写入分段的文件，而不是将它们添加到内存中的列表中，每个文件覆盖一些素数块(相当大，但在很容易加载到内存的范围内)。也许作为第一行，一些关于文件中最大/最小素数的信息。

在GeneratePrimeNumbers中，从保存最大素数的页面开始(仅将该页面从文件中加载到列表中，选择一个C#数据类型，该数据类型有O(1)时间用于.Contains，我认为HashSet对此很有帮助)，当您反向工作并进入一个新段时，删除当前素数页的列表并加载新的素数页。这将解决您的内存使用问题。如果确保每个页面包含相同数量的素数(或者上一页可能是部分的最大值)，那么您可以重用现有的列表，或者使用容量==将列表初始化为页面的大小。不管您使用什么数据结构，它可能在构造函数中有一个容量选项，您希望传递这个选项，因为它将确保它预先请求所需的内存量。如果您有300个素数，并且没有设置capcity，那么所发生的是列表的内部数组大小在添加到它时加倍。例如，当它跨越256时，它在内部创建一个新的512项数组，并将这256项复制到新大小512数组中。这意味着当跨越这样的边界时，列表使用的内存是内存的三倍，因为它既有旧的数组，也有新的数组，是旧数组的2倍。复制完成后，它不需要旧的数组。重点是，如果你不预先设置容量，那么当你只需要大约三分之一的空闲内存时，你就有可能摆脱内存异常。

我可能会让GeneratePrimeNumbers只检查预先存在的文件，如果传入的数量更大，那么只需跳到现有的最大页面，并编写更多的页面，直到该值。我可能有一个索引文件，列出页面和起始/结束素数，这样您就不必读取一堆大型文件来执行此检查，但我认为您可以通过将每个文件中的start/end作为第一行，只读取第一行，然后关闭该文件来完成。