一、是否为质数的定义
质数是指只能被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;
}
五、总结
判断质数是一项基本的数学问题，同时也是算法领域的一大难题。通过对判断质数的优化方法的学习和代码实现，我们可以更好地理解算法中的思想和技巧，同时也能够增强对基本数据类型的理解。
原创文章，作者：小蓝，如若转载，请注明出处：https://www.506064.com/n/230200.html
微信扫一扫 
支付宝扫一扫 