一、判断素数(基础版):
通过从2到 ( n ) \sqrt(n) (n)线性遍历的方法来判断一个数是否为素数:
#include <iostream>bool isPrime(int n) {if (n <= 1) {return false;}for (int i = 2; i * i <= n; i++) {if (n % i == 0) {return false;}}return true;
}int main() {int num;std::cout << "请输入一个整数: ";std::cin >> num;if (isPrime(num)) {std::cout << num << " 是素数。" << std::endl;} else {std::cout << num << " 不是素数。" << std::endl;}return 0;
}
在这个程序中:
- 边界:小于等于1的数不是素数
- 条件:如果在遍历过程中发现
n
能被某个数整除,那么n
不是素数,函数返回false
。 - 如果遍历完没有发现这样的数,则
n
是素数,函数返回true
。
二、分解质因数(基础版):
从2开始依次去查找n的因数(后面可以配合素数的判断方法进行改进)
#include <iostream>
#include <vector>using namespace std;vector<int> primeFactorization(int n) {vector<int> factors;int divisor = 2;while (n >= 2) {if (n % divisor == 0) {factors.push_back(divisor);n = n / divisor;} else {divisor++;}}return factors;
}int main() {int number;cout << "Enter a number to factorize: ";cin >> number;vector<int> result = primeFactorization(number);cout << "Prime factorization of " << number << " is: ";for (int i = 0; i < result.size(); i++) {cout << result[i];if (i!= result.size() - 1) {cout << " * ";}}cout << endl;return 0;
}
在这段代码中:
primeFactorization
函数:- 它接受一个整数
n
。 - 从
2
开始作为除数,因为2
是最小的质数。 - 只要
n
大于等于2
,就检查n
是否能被当前除数divisor
整除。如果能整除,就把divisor
添加到factors
向量中,并将n
更新为n
除以divisor
的结果。如果不能整除,就增加divisor
的值。
- 它接受一个整数
三、分解质因数(优化版)
#include <iostream>
#include <vector>using namespace std;bool isPrime(int n) {if (n <= 1) {return false;}for (int i = 2; i * i <= n; i++) {if (n % i == 0) {return false;}}return true;
}
vector<int> primeFactorization(int n) {vector<int> factors;int divisor = 2;while (n >= 2) {if(isPrime(n)){factors.push_back(n);break;}if (n % divisor == 0) {factors.push_back(divisor);n = n / divisor;} else {divisor++;}}return factors;
}int main() {int number;cout << "Enter a number to factorize: ";cin >> number;vector<int> result = primeFactorization(number);cout << "Prime factorization of " << number << " is: ";for (int i = 0; i < result.size(); i++) {cout << result[i];if (i!= result.size() - 1) {cout << " * ";}}cout << endl;return 0;
}
在primeFactorization
中,每次进行因数判断前,先判断当前的n是否为素数,如果时素数就放入结果数组并返回。