通过 Eratosthenes Sieve C# 生成素数

Question

我正在尝试解决 Project Euler 的问题 3，发现 here. I would like to solve it by generating a List of Primes using Eratosthene's Sieve (found here. 我离完成问题还差得很远，但我运行遇到了一个小问题...

下面是我为此编写的代码。但是，当我运行这段代码时，它会停止我的计算机，并在进一步停止之前输出 2。显然是运行ning，但它似乎并没有做对。在它输出列表之前，它应该让我知道（只是检查挂起是否在输出之前）它已经完成分配列表...

如果你不确定发生了什么，你能给我一些指导来深入研究代码并调试它的不同行吗？我在不同的地方试过 Console.WriteLine，但它似乎没有响应代码。

using System;
using System.Collections.Generic;
using System.Linq;

public class Program
{
    static void Main(string[] args)
    {
        long maxNum = 100;
        double maxSqrt = Math.Floor(Math.Sqrt(maxNum));
        long basePrime;
        // Make a list from 2 to maxNum
        List<long> numberList = new List<long>();
        List<long> sievedList = new List<long>();
        for (long i = 2; i <= maxNum; i++) numberList.Add(i);
        // Evaluate the first number of the list, if it is < maxSqrt skip it, create a list of multiples and Except them from numberList, else, numberList is completely Prime Factors

        foreach (long number in numberList.Skip(1))
        {
            basePrime = numberList[0];
            Console.WriteLine(basePrime);
            while (number < maxSqrt)
                {
                    if (number % basePrime == 0)
                    {
                        sievedList.Add(number);
                    }
                    numberList = numberList.Except(sievedList).ToList();
                    sievedList.Clear();
                }
        }
    Console.WriteLine("Finished Allocating Primes");   
    numberList.ForEach(Console.WriteLine);
    }
}

Answer 1

对于您眼前的问题，请将 while 更改为 if。

但是你的代码还有其他问题。

您的 numberedList 只是一个从 2 到 maxNum 的整数列表，您正在使用 for 循环填充这些整数。然后你遍历列表。只需使用 for 循环中的计数器即可。为了记录哪些数字是质数，BitArray(Int32, Boolean) 效果很好。
这也允许摆脱昂贵的 LINQ 扩展。当您找到一个非质数时，只需更改它在 BitArray 中的索引即可。当您找到质数时，将其添加到列表中；

Answer 2

灵感来自： Laziness in Python - Computerphile 我将其翻译成 C#：

using System;
using System.Collections.Generic;
using System.Linq;

namespace GenertatorTest
{
    class Program
    {
        /// <summary>
        /// Natural Numbers Genarator
        /// </summary>
        /// <param name="first">first number in the sequence</param>
        /// <returns>the sequence: first, first + 1, first + 2, ... ∞</returns>
        static IEnumerable<int> natural(int begin)
        {
            yield return begin;
            foreach (var item in natural(begin + 1))
            {
                yield return item;
            }
        }

        /// <summary>
        /// Primary Numbers Genarator
        /// </summary>
        /// <param name="nums">natural numbers sequence which we want to apply  Eratosthene's Sieve on</param>
        /// <returns>infinite primary numbers sequence</returns>
        static IEnumerable<int> primes(IEnumerable<int> nums)
        {
            int p = nums.ElementAt(0);
            yield return p;
            foreach (var item in primes(nums.Where(x => x % p != 0)))
            {
                yield return item;
            }
        }

        static void Main(string[] args)
        {
            foreach (var item in primes(natural(2)))
            {
                Console.WriteLine(item);
                //it is infinite sequence
                //so you cant just run through. 
                Console.ReadKey();
            }
        }
    }
}

其实这段代码比你想象的要优雅。我们这里唯一缺少的语法糖是 yield from，C# 似乎不支持它。

通过 Eratosthenes Sieve C# 生成素数

Generate Prime Numbers via Eratosthene's Sieve C#

c#

primes