C#试除法-前n个素数.逻辑错误

本文关键字:错误 除法 | 更新日期: 2023-09-27 18:22:02

在一门课程中,一个问题是列出前n个素数。显然,我们应该在数组中保存素数的同时实现试除法,以减少所需的除法数量。起初我误解了,但得到了一个工作较慢的解决方案,使用一个单独的函数来测试素性,但我想以我应该做的方式实现它。

下面是我的尝试,去掉了不相关的代码,比如输入测试。

using System;
namespace PrimeNumbers
{
    class MainClass
    {
        public static void Main (string[] args)
        {
            Console.Write("How many primes?'n");
            string s = Console.ReadLine();
            uint N;
            UInt32.TryParse(s, out N)
            uint[] PrimeTable = new uint[N];
            PrimeTable[0] = 2;
            for (uint i=1; i < N; i++)//loop n spaces in array, [0] set already so i starts from 1
            {
                uint j = PrimeTable[i -1] + 1;//sets j bigger than biggest prime so far
                bool isPrime = false;// Just a condition to allow the loop to break???(Is that right?)
                while (!isPrime)//so loop continues until a break is hit
                {
                    isPrime = true;//to ensure that the loop executes
                    for(uint k=0; k < i; k++)//want to divide by first i primes
                    {
                        if (PrimeTable[k] == 0) break;//try to avoid divide by zero - unnecessary
                        if (j % PrimeTable[k] == 0)//zero remainder means not prime so break and increment j
                        {
                            isPrime = false;
                            break;
                        }
                    } 
                    j++;//j increment mentioned above
                }
                PrimeTable[i] = j; //not different if this is enclosed in brace above
            }
            for (uint i = 0; i < N; i++)
                Console.Write(PrimeTable[i] + " ");
            Console.ReadLine();
        }
    }
}

我的评论是我试图描述我认为代码正在做什么,我尝试了很多小的更改,通常在运行时会导致除以零的错误,所以我添加了一个测试,但我认为这不应该是必要的。(在尝试改变循环条件时,我也遇到了几个超出范围的错误。)

我研究了关于堆栈交换的几个问题,特别是:查找素数的程序第一个答案使用了不同的方法,第二个接近我想要的,但确切的情况在Nick Larsson的评论中:

你可以通过追踪素数来加快速度试图通过这些来划分。

C#未显示在此处:http://rosettacode.org/wiki/Sequence_of_primes_by_Trial_Division#Python

我见过很多其他方法和算法,比如Eratosthenes sive和GNF,但我真的只想用这种方式实现它,因为我认为我的问题在于程序逻辑,我不明白为什么它不起作用。感谢

C#试除法-前n个素数.逻辑错误

以下应该可以解决您的问题:

    for (uint i = 1; i < numberOfPrimes; i++)//loop n spaces in array, [0] set already so i starts from 1
    {
        uint j = PrimeTable[i - 1] + 1;//sets j bigger than biggest prime so far
        bool isPrime = false;// Just a condition to allow the loop to break???(Is that right?)
        while (!isPrime)//so loop continues until a break is hit
        {
            isPrime = true;//to ensure that the loop executes
            for (uint k = 0; k < i; k++)//want to divide by first i primes
            {
                if (PrimeTable[k] == 0) break;//try to avoid divide by zero - unnecessary
                if (j % PrimeTable[k] == 0)//zero remainder means not prime so break and increment j
                {
                    isPrime = false;
                    j++; 
                    break; 
                }
            }
        }
        PrimeTable[i] = j; 
    }

我所做的主要改变是将变量j的增量移动到条件素数检查中。这是因为,当前值不是素数,所以我们要检查下一个素数,并且必须在进入循环之前移动到下一个候选者。

进行检查后,您的代码正在递增。这意味着,当你找到一个素数候选者时,你会递增到下一个候选者,并将其指定为你的素数。例如,当j=3时,它将通过条件,isPrime仍将=true,但随后j++将其递增到4,这将把它添加到PrimeTable中。

有道理吗?

这可能不是一个很好的答案,但您可能想看看这个实现,看看是否能发现您的不同之处。

int primesCount = 10;
List<uint> primes = new List<uint>() { 2u };
for (uint n = 3u;; n += 2u)
{
    if (primes.TakeWhile(u => u * u <= n).All(u => n % u != 0))
    {
        primes.Add(n);
    }
    if (primes.Count() >= primesCount)
    {
        break;
    }
}

这正确且有效地计算第一CCD_ 1素数。