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,但我真的只想用这种方式实现它,因为我认为我的问题在于程序逻辑,我不明白为什么它不起作用。感谢
以下应该可以解决您的问题:
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素数。