C++判断质数的实现方法

一、是否为质数的定义

质数是指只能被1和自身整除的正整数。判断一个数是否为质数，即判断它能否被除1和自身以外的正整数整除。

二、暴力法判断质数

暴力法是一种最原始的判断质数的方法，即对于一个数n，依次判断2~n-1是否能够整除n。如果能整除，则认为n不是质数；如果不能整除，则认为n是质数。

bool isPrime(int n) {
    if(n < 2) return false; // 小于2的数不是质数
    for(int i = 2; i < n; i++) {
        if(n % i == 0) return false;
    }
    return true;
}

这种方法的时间复杂度为O(n)，运行时间随着n的增大而增大，不适用于大数的判断。需要使用更高效的算法。

三、优化判断质数的方法

1. 去掉偶数判断

所有大于2的偶数都不是质数，因为它们都可以被2整除。所以，在判断一个数是否为质数时，可以先判断它是否是2，如果是2，则是质数；如果不是2，则去掉偶数进行判断。

bool isPrime(int n) {
    if(n < 2) return false; // 小于2的数不是质数
    if(n == 2) return true; // 2是质数
    if(n % 2 == 0) return false; // 去掉偶数判断
    for(int i = 3; i <= sqrt(n); i += 2) { // 只判断奇数
        if(n % i == 0) return false; 
    }
    return true;
}

在上面的代码中，倒数第二行中的i += 2是因为质数不可能是偶数，所以可以只判断奇数。而sqrt(n)的范围是因为，在2~sqrt(n)之间的数，如果不能整除n，那么大于sqrt(n)的数也不可能整除n。所以只需要判断到sqrt(n)。

2. 去掉6的倍数判断

6的倍数两侧都是偶数，不是质数。在去掉偶数后，如果判断的数能够被3整除，那么它一定不是质数。因为质数只能是6n+1或6n-1的形式，所以只需要判断6n+1和6n-1的数是否为质数。

bool isPrime(int n) {
    if(n < 2) return false; // 小于2的数不是质数
    if(n == 2 || n == 3) return true; // 2和3是质数
    if(n % 6 != 1 && n % 6 != 5) return false; // 去掉6的倍数判断
    for(int i = 5; i <= sqrt(n); i += 6) {
        if(n % i == 0 || n % (i + 2) == 0) return false; // 只判断6n+1和6n-1的数
    }
    return true;
}

四、完整代码

经过上面的优化，判断质数的方法已经相对高效了。下面是完整代码：

#include <iostream>
#include <cmath>
using namespace std;

bool isPrime(int n) {
    if(n < 2) return false; // 小于2的数不是质数
    if(n == 2 || n == 3) return true; // 2和3是质数
    if(n % 6 != 1 && n % 6 != 5) return false; // 去掉6的倍数判断
    for(int i = 5; i <= sqrt(n); i += 6) {
        if(n % i == 0 || n % (i + 2) == 0) return false; // 只判断6n+1和6n-1的数
    }
    return true;
}

int main() {
    int n;
    cout << "请输入一个正整数：" << endl;
    cin >> n;
    if(isPrime(n)) {
        cout << n << "是质数。" << endl;
    } else {
        cout << n << "不是质数。" << endl;
    }
    return 0;
}

五、总结

判断质数是一项基本的数学问题，同时也是算法领域的一大难题。通过对判断质数的优化方法的学习和代码实现，我们可以更好地理解算法中的思想和技巧，同时也能够增强对基本数据类型的理解。