C语言程序判断一个数是否为质数

质数是指只能被1和自身整除的数。一个数的因数是可以整除它的数。

前十个质数是：2, 3, 5, 7, 11, 13, 17, 23, 29, 31。

非质数称为合数。合数是可以被多个数整除的数。

除了质数和合数之外，还有1，它既不是质数也不是合数，因为它只能被自身整除。

如何检查一个数是质数还是合数？要检查一个数是否为质数，需要检查以下两个条件：

1) 它必须是一个大于1的整数。

2) 它只能有两个因数，即1和自身。

如果满足这两个条件，则该数为质数。

在我们的程序中，我们将通过将该数除以小于该数的每个数来进行检查。如果任何小于给定数的数都能整除它，则它不是质数。否则，它是一个质数。

示例

让我们以两个数为例，并使用此方法检查它们是否为质数。

Input − Number1 − 42
Output − 42 is not a prime number

逻辑

我们将42除以每个大于1且小于42的数。所以：

42/2 = 21，即42可以被2整除，这意味着42不是质数，因为它可以被其他数整除。

Input − Number2 − 7
Output − 7 is a prime number

逻辑解释

我们将7除以每个大于1且小于7的数。所以：

7不能被2整除，因此代码将检查下一个数，即3。

7不能被3整除，因此代码将检查下一个数，即4。

7不能被4整除，因此代码将检查下一个数，即5。

7不能被5整除，因此代码将检查下一个数，即6。

7不能被6整除，这意味着7只能被1和7整除，这意味着7是一个质数。

看看上面的逻辑，如果数字超过1000甚至100000，那么程序将需要进行那么多次循环迭代，这种方法将需要大量的计算时间。因此，为了减少迭代次数，必须有更好的方法。

一个优化的解决方案是只运行for循环到一半。这意味着如果数字是77，循环将只运行到38。这将减少所需的迭代次数，因此我们将使用此算法来创建我们的程序。

示例

#include <stdio.h>
int main() {
   int num = 33, flag = 0;
   for(int i=2 ; i < num/2 ; i++) {
      if(num%i == 0) {
         printf("%d is not a prime number", num);
         flag = 1;
         break;
      }
   }
   if(flag == 0) {
      printf("%d is a prime number", num);
   }
}

输出

33 is a prime number

sudhir sharma

更新于：2023年11月7日

4万+ 次浏览

开启您的职业生涯

完成课程获得认证

开始学习