C#求第N个素数

本文关键字：求第 | 更新日期: 2023-09-27 18:16:10

可能重复：
素数公式

我正试图在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;
                }
            }
        }
    }
}

C#求第N个素数

这不是埃拉托斯梯尼之筛的工作原理，你应该阅读维基百科文章中的这一部分：

  • 创建一个从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;
        }
    }
}

积分转到罗塞塔代码

这是因为你的算法被严重破坏了——当你需要测试小于当前数字的所有*素数时，你只是在测试不能被2、3、5和7整除的数字。

快速阅读一下Fun With Prime Numbers，它有一些更直观的查找素数的方法，尽管查找素数的算法通常不适合Stack Overflow。

(*(实际上，你可以测试比这更少的素数，但我的观点是，测试有限数量的素数是行不通的

更新：您的算法不是Eratosthenes筛，它只是针对与在n = 120的情况下筛相同的数字进行测试。你应该再读一次维基百科文章的"算法描述"部分。

下面的代码打印所有素数，直到1000000

        private static void FindPrimeNumber()
        {
            int topNumber = 1000000;
            var numbers = new BitArray(topNumber, true);
            for(int i = 2; i < topNumber; i++)
                if(numbers[i])
                {
                    for(int j = i * 2; j < topNumber; j += i)
                        numbers[j] = false;
                }
            int primes = 0;
            for(int i = 1; i < topNumber; i++)
                if(numbers[i])
                {
                    primes++;
                    Console.Out.WriteLine(i);
                }
            Console.WriteLine();
            Console.Out.WriteLine(primes + " out of " + topNumber + " prime numbers found.");
            Console.ReadLine();
        }

您需要将该数字与所有数字除以其平方根。

例如，你需要用sqrt(100(=10除以100，如果它不能除以，那么它就是一个素数，所以你只需要做

for(int i = 2; i <= Math.Sqrt(number); i++)
{
    if(number%i == 0) return false;
}
return true;
相关文章：