C# 埃拉托色尼筛法

Question

我写了这段代码来寻找质数，它运行良好，但计算速度非常慢.....我做错了吗？我知道我可能真的做错了，但请帮助我!非常感谢!

using System;
using System.Collections.Generic;

namespace Primenumbers
{
    class MainClass
    {
        public static void Main (string[] args)
        {    
            List<int> NoPrime = new List<int>();

            for(int x = 2; x < 10000;x++)
            {
                for(int y = x * 2;y < 10000;y = y + x)
                {    
                    if(!NoPrime.Contains(y))
                    {
                        NoPrime.Add(y);
                    }    
                }    
            }

            for(int z = 2; z < 10000;z++)
            {
                if(!NoPrime.Contains(z))
                {
                    Console.WriteLine(z);
                }
            }
        }
    }
}

编辑:这是新代码，我将“List”更改为“HashSet”并添加了一个计数器来获取所有素数的总和。非常感谢所有评论/回答的人，你们太棒了!

using System;
using System.Collections.Generic;

class MainClass
{
    public static void Main (string[] args)
    {
        HashSet<int> NoPrime = new HashSet<int>();

        long count = 0;
        int n = 2000000;

        for(int x = 2; x < n;x++)
        {
            for(int y = x * 2;y < n;y = y + x)
            {

            if(!NoPrime.Contains(y))
            {
                NoPrime.Add(y);
            }
        }

        for(int z = 2; z < n;z++)
        {
            if(!NoPrime.Contains(z))
            {
                Console.WriteLine(z);
                count = count + z;
            }
        }

        Console.WriteLine("Sum is: " + count);
    }
}

Answer 1

您的代码的复杂性介于 O(n * (n log n)) 和 O(n ^ 3)(不确定)之间，而不是 O(n log log n)(参见 Sieve of Eratosthenes: Complexity)。

• 线性搜索 NoPrime列表(给复杂性额外的 n)
• 在外循环中缺少“查找下一个素数”检查 - 因此内循环的复杂度超过 O(log log n)

修复:

改为Dictionary<int,bool> (或者更好的是 HashSet<int>，如评论中所建议的那样)以获得 Contains 的 O(1) 复杂度.或者，您可以通过分配大型 bool 数组来直接实现算法。对于每个数字和标记项目 true (再次给出 O(1) 检查数字是否为质数)。

在外部循环中添加检查以跳过 x 不是素数的内部迭代。