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

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```  

输出

11 is prime number

时间复杂度: 只有计算(n-1)的阶乘并检查它是否为0或1的O(N)复杂度,使用%运算符只需要常数时间
辅助空间: O(1)

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程

C++ 示例