时间戳

首页 > 解决方案 > 质数检查器c#中的错误

c# - 质数检查器c#中的错误

问题描述

我写了这段代码来检查一个数字是否是素数，但它不起作用，我的意思是输出是：

1 不是质数

2是质数

3 不是质数

4是质数等等。

请你能告诉我我的错误是什么，谢谢

ps我写number =1了因为我不能将一个数字除以0。

for( int number =1;number <101 && number >0;number++)
{
    int reimander = (number / 1) & (number / number);
    Console.WriteLine(number +(reimander == 0 ? " is a prime number" : " isn't a prime number"));
}

标签： c#

解决方案

正如Daisy Shipton所述，您的检查不足以确定您的号码是否为素数。

为了使一个数成为素数，它必须只能被一个或它自己整除。这意味着您应该检查 3 和您正在检查的素数事实之间的每个数字的除法。

实际上，您不需要检查 3 和您的数字之间的每个数字，而只需检查 3 和您的数字平方之间的数字。

事实上，如果一个整数 k 是合数（非素数），它可以写成两个整数 p 和 q 的乘积：k = p*q

然而这两个数字 p 和 q 不能同时大于 k 的平方 (s)，因为在这种情况下，它们的乘积应该大于 k。如果 p > s 且 q > s，则 pxq > sxs，即 pxq > k。

代码应该看起来像这样（未经测试）：

public static bool IsPrime(int number)
    {
        /****** easy check before going to long calculations *******/
        if (number < 2) return false; // A prime number is always greater than 1
        if (number == 2) return true; // 2 is prime
        if (number % 2 == 0) return false; // Even numbers except 2 are not prime

        /****** if your number is Odd and not equals to 2, 
                you have to check every numbers between 3 
                and the square of your number               *******/
        var boundary = (int)Math.Floor(Math.Sqrt(number)); // square of your number

        // increment i by 2 because you already checked that your number is Odd 
        // and therefore not divisible by an Even number
        for (int i = 3; i <= boundary; i += 2) 
        {
            if (number % i == 0) return false; // the number can be devided by an other => COMPOSITE number
        }
        return true; // number at least equals to 3, divisible only by one or itself => PRIME number
    }

现在您可以为每个要测试的数字做一个基本循环并调用它们的这个函数。它们有很多计算一系列素数的方法，但它们的理解也更加复杂。

 for (int number = 1; number < 101 && number > 0; number++)
 {
      Console.WriteLine(number + " is " + (IsPrime(number) ? "prime" : "not prime"));
 }

推荐阅读