C#查找第N个素数

Question

可能重复:素
数公式

我试图在c#中编写一些代码,它会给我第n个素数但是一旦我的代码超过121作为素数,它就会开始给我错误的数字.

现在这可能是我已经将我的代码基于错误的算法,但我想在这里问一下,看看我做错了什么.

代码询问nth prime 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;
                }
            }
        }
    }
}

Answer 1

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

• 创建从2到n的连续整数列表:(2,3,4,...,n).
• 最初,让p等于2,即第一个素数.
• 从p开始,以p为增量进行计数,并在列表中将每个数字标记为大于p本身.这些数字将是2p,3p,4p等; 请注意,其中一些可能已被标记.
• 在列表中找到未标记的第一个大于p的数字; 让p现在等于这个数字(这是下一个素数).
• 如果列表中没有更多未标记的数字,请停止.否则,从步骤3开始重复.

所以基本上你认为的限制(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