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

查看:68
本文介绍了通过Eratosthene的筛子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屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆