通过Eratosthene的筛子C#生成素数 [英] Generate Prime Numbers via Eratosthene's Sieve C#

问题描述

我正在尝试解决Project Euler的问题3，Foundhere.我想通过使用Eratosthene筛子生成素数列表来解决它(Foundhere.我远未完成问题，但我遇到了一个小问题...

下面是我为此编写的代码。然而，当我运行这段代码时，它会停止我的计算机，并输出一个2，然后再延迟一些。它显然在运行，但似乎做得不对。在它输出列表之前，它应该让我知道(只是检查是否在输出之前挂断)它已经完成了列表的分配...

如果您不确定发生了什么，您能给我一些指导，让我深入了解代码并调试它的不同行吗？我在不同的区域尝试过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);
    }
}

推荐答案

对于您的紧急问题，请将while更改为if。

但是，您的代码还存在其他问题。

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

这篇关于通过Eratosthene的筛子C#生成素数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！