C++程序检查一个数是否为质数

给定一个正整数N。任务是编写一个C++程序来检查这个数是不是质数。

C++程序检查一个数是否为质数

定义：

质数是一个大于1的自然数，除了1和本身之外没有其他正约数。前几个质数是{2,3,5,7,11 ……}。

解决这个问题的思路是使用for循环从2到sqrt(N)遍历所有数字，并且针对每个数字检查它是否可以整除N。如果我们找到任何可以整除N的数字，就返回false。如果我们在2和sqrt（N）之间没有找到任何整除N的数字，那么它就意味着N是质数，我们将返回True。

为什么我们选择sqrt(N)?

原因是一个数的最小约数和大于一的约数都不可能超过N的平方根。并且当我们找到一种因子时就停止。例如，如果N是49，则最小因子是7。对于15而言，最小因子是3。

下面是检查一个数是否为质数的C++程序:

// C++ program to check if a
// number is prime
#include <iostream>
#include <math.h>
using namespace std;
  
int main()
{
    int n, i, flag = 1;
  
    // Ask user for input
    cout << "Enter a number: ";
  
    // Store input number in a variable
    cin >> n;
  
    // Iterate from 2 to sqrt(n)
    for (i = 2; i <= sqrt(n); i++) {
  
        // If n is divisible by any number between
        // 2 and n/2, it is not prime
        if (n % i == 0) {
            flag = 0;
            break;
        }
    }
  
    if (n <= 1)
        flag = 0;
  
    if (flag == 1) {
        cout << n << " is a prime number";
    }
    else {
        cout << n << " is not a prime number";
    }
  
    return 0;
}
  
// This code is contributed by shivanisinghss2110.```

输出 :

Enter a number: 11
11 is a prime number

时间复杂度： O(n 1/2 )

辅助空间： O(1)

方法2： 基于Wilsons定理的优化方法，复杂度为 O(N)

如果 ((n-1)!+1) % n == 0，则n是质数，否则它不是质数。

例如：

输入： 11

输出： 11是质数

解释： (11-1)! + 1 = 3628801

3628801 % 11 = 0

输入： 8

输出： 8不是质数

解释： (8-1)! + 1 = 5041

5041 % 8 = 1

上述方法的实现：

// C++ program to check whether number is prime or not
#include <iostream>
using namespace std;
  
int main()
{
    // code
    int n = 11;
    int m = n - 1;
    int factm = 1;
    // find factorial of n-1
    for (int i = 1; i <= m; i++) {
        factm *= i;
    }
  
    // add 1 to (n-1)!
    int factn = factm + 1;
    if (factn % n == 0) {
        // if remainder is 0
        cout << n << " is prime number";
    }
    else {
        cout << n << " is not prime";
    }
    return 0;
}
// this code is contributed by devendra solunke```

输出