检查质数

Question

我在一项任务上遇到问题。如果数字是质数，我需要找到并提醒用户。

下面是我的代码：

int a = Convert.ToInt32(number);

if (a % 2 !=0 )
{
    for (int i = 2; i <= a; i++)
    {
        if (a % i == 0)
        {
            Console.WriteLine("not prime");
        }
        else
        {
            Console.WriteLine("prime");
        }
        Console.WriteLine();
    }
}
else
{
    Console.WriteLine("not prime");
}
Console.ReadLine();

我哪里出了问题，我该如何修复它？

Answer 1

素数可以被1整除，你需要检查数字是否恰好有两个除数，从1到1，那么它就是素数。

 int devisors = 0;
 for (int i = 1; i <= a; i++)
     if (a % i == 0)                        
          devisors++;

 if (devisors == 2)                 
     Console.WriteLine("prime");
 else
     Console.WriteLine("not prime");

你可以跳过一次迭代，因为我们知道所有的整数都可以被1整除，然后你就可以精确地得到素数的除数。因为1只有一个因子，所以我们需要跳过它，因为它不是质数。所以条件是数只有一个因子，而不是1，并且数不应该是1，因为1不是质数。

 int devisors = 0;
 for (int i = 2; i <= a; i++)
     if (a % i == 0)                        
          devisors++;

 if (a != 1 && devisors == 1)                 
     Console.WriteLine("prime");
 else
     Console.WriteLine("not prime");

Answer 2

实际上并不需要%2检查。适当修改：

int a = Convert.ToInt32(number);

bool prime = true;
if (i == 1) prime = false;
for (int i = 2; prime && i < a; i++)
    if (a % i == 0) prime = false;
if (prime) Console.WriteLine("prime");
else Console.WriteLine("not prime");
Console.ReadLine();

Answer 3

假设你的代码输出了很多消息，这些消息看起来杂乱无章，毫无意义？有3个关键问题：

当你决定它不能是素数时，如果你假设它可能不是素数，请参阅下面代码中的注释。

• 你正在与a本身进行比较，它总是可以被a整除，条件中的<=需要是<

代码：

int a = Convert.ToInt32(number);

if (a % 2 != 0)
{
    for (int i = 3 i < a; i += 2) // we can skip all the even numbers (minor optimization)
    {
        if (a % i == 0)
        {
            Console.WriteLine("not prime");
            goto escape; // we want to break out of this loop
        }
        // we know it isn't divisible by i or any primes smaller than i, but that doesn't mean it isn't divisible by something else bigger than i, so keep looping 
    }
    // checked ALL numbers, must be Prime
    Console.WriteLine("prime");
}
else
{
    Console.WriteLine("not prime");
}
escape:
Console.ReadLine();

正如其他人所提到的，您只能循环到a的平方根，方法是预先计算平方根并替换下面这一行：

for (int i = 3 i < a; i += 2)

有了这个：

float sqrRoot = (Int)Math.Sqrt((float)a);
for (int i = 3 i <= sqrRoot; i += 2)

每次计算都很重要，否则你的程序会运行得更慢，而不是更快，因为每次迭代都会涉及一个平方根操作。

如果你不喜欢goto语句(我喜欢goto语句)，发表一个评论，我会把它替换成一个突破布尔值(或者看杜克林最近的回答)。