C# 查找第 N 个素数

这个问题在这里已经有了答案:




9年前关闭。






我正在尝试用 c# 编写一些代码，它会给我第 n 个质数，但是一旦我的代码超过 121 作为质数，它就会开始给我不正确的数字。

现在这可能是我的代码基于错误的算法，但我想在这里问一下，看看我是否做错了什么。

代码要求第 n 个素数 10001 - 输出:43751(我知道这是错误的)

这里的任何地方都是我的代码。

int[] p;
int x = 0;
p = new int[10002];
for (int i = 0; i < 1000000; i++)
if (i % 2 != 0)
{
    if (i % 3 != 0)
    {
        if (i % 5 != 0)
        {
            if (i % 7 != 0)
            {
                p[x] = i;
                x++;
                if (x == 10001)
                {
                    Console.WriteLine("{0}", i);
                    break;
                }
            }
        }
    }
}

最佳答案

这不是 Eratosthenes 筛子的工作原理，您应该阅读维基百科文章中的这一部分:



所以基本上你认为的限制( 121 ，来自你的评论)只是他们在动画 .gif 中使用的一个例子。

这是此方法的 C# 实现:

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

namespace sieve
{
    class Program
    {
        static void Main(string[] args)
        {
            int maxprime = int.Parse(args[0]);
            ArrayList primelist = sieve(maxprime);

            foreach (int prime in primelist)
                Console.WriteLine(prime);

            Console.WriteLine("Count = " + primelist.Count);
            Console.ReadLine();
        }

        static ArrayList sieve(int arg_max_prime)
        {
            BitArray al = new BitArray(arg_max_prime, true);

            int lastprime = 1;
            int lastprimeSquare = 1;

            while (lastprimeSquare <= arg_max_prime)
            {
                lastprime++;

                while (!(bool)al[lastprime])
                    lastprime++;

                lastprimeSquare = lastprime * lastprime;

                for (int i = lastprimeSquare; i < arg_max_prime; i += lastprime)
                    if (i > 0)
                        al[i] = false;
            }

            ArrayList sieve_2_return = new ArrayList();

            for (int i = 2; i < arg_max_prime; i++)
                if (al[i])
                    sieve_2_return.Add(i);

            return sieve_2_return;
        }
    }
}

学分转到 Rosetta Code

关于C# 查找第 N 个素数，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/8295088/