c++求素数
素数是指在大于1的自然数中，除了1和本身，没有其他因数的自然数。素数在数学和计算机科学中都有着重要的应用。在计算机科学中，求素数是一个经典的问题，也是算法设计和优化的重要研究方向。
本文将从多个角度分析如何用C++求素数，包括素数的定义、素数的判定方法、C++中的求素数算法以及优化策略等。
素数的定义
素数是指在大于1的自然数中，除了1和本身，没有其他因数的自然数。比如2、3、5、7、11、13等就是素数，而4、6、8、9、10、12等就不是素数。
素数的判定方法
判断一个数是否为素数，最简单的方法就是试除法。即将这个数除以2到它的平方根之间的所有自然数，如果都无法整除，那么就是素数。代码如下：
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;
}
C++中的求素数算法
C++中有多种求素数的算法，常见的有埃氏筛法、欧拉筛法、线性筛法等。
埃氏筛法的思路是先将所有数标记为素数，然后从2开始，将所有2的倍数标记为合数，再从3开始，将所有3的倍数标记为合数，以此类推，直到sqrt(n)。最后，所有未标记的数就是素数。代码如下：
vector
vector
vector
for (int i = 2; i * i <= n; i++) {
if (isPrime[i]) {
for (int j = i * i; j <= n; j += i) {
isPrime[j] = false;
}
}
}
for (int i = 2; i <= n; i++) {
if (isPrime[i]) primes.push_back(i);
}
return primes;
}
欧拉筛法是对埃氏筛法的优化。它的思路是先将所有数标记为素数，然后从2开始，将所有2的倍数标记为合数，同时将所有2的倍数的质因子2去掉，再从3开始，将所有3的倍数标记为合数，同时将所有3的倍数的质因子3去掉，以此类推，直到sqrt(n)。最后，所有未标记的数就是素数。代码如下：
vector
vector
vector
for (int i = 2; i <= n; i++) {
if (isPrime[i]) primes.push_back(i);
for (int j = 0; j < primes.size() && i * primes[j] <= n; j++) {
isPrime[i * primes[j]] = false;
if (i % primes[j] == 0) break;
}
}
return primes;
}
线性筛法是对欧拉筛法的进一步优化。它的思路是先将所有数标记为素数，同时将所有素数存入一个数组中。然后对于每个合数，找到它最小的质因子，将它标记为合数，并将它乘上它的最小质因子得到下一个合数。这样，每个合数只会被它的最小质因子筛掉一次，而每个数都只会被它的最小质因子筛掉一次，时间复杂度为O(n)。代码如下：
vector
vector
vector
for (int i = 2; i <= n; i++) {
if (minPrime[i] == 0) {
minPrime[i] = i;
primes.push_back(i);
}
for (int j = 0; j < primes.size() && primes[j] <= minPrime[i] && i * primes[j] <= n; j++) {
minPrime[i * primes[j]] = primes[j];
}
}
return primes;
}
优化策略
求素数是一个经典的问题，也是算法设计和优化的重要研究方向。下面简要介绍几种优化策略。
1. 去除偶数。素数除了2以外，都是奇数。因此，可以先判断2，然后只对奇数进行判断。
2. 减小判定范围。对于一个数n，如果它不是素数，那么它的质因子一定小于等于sqrt(n)。因此，只需要对2到sqrt(n)之间的数进行判断，可以减小判定范围。
3. 使用位运算。位运算比算术运算更快。可以使用位运算来代替除法和取模运算，从而提高效率。
4. 多线程并发。在多核CPU上，可以使用多线程并发来加速求素数的过程。