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加上一个数字，那么程序将需要执行这么多次迭代。这种方法需要大量的计算时间。为了减少迭代次数，必须有更好的办法。

优化的解决方案是只运行一半的循环。这意味着如果数字是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);
   }
}