★判断素数的几种方法（由易到难，由慢到快）
素数的定义：
素数，又称为质数，指的是“大于1的整数中，只能被1和这个数本身整除的数”。换句话说，素数是只有两个正约数（1和本身）的自然数。素数在数论中有着重要的地位，且素数的个数是无限的。例如，2、3、5、7、11、13等都是素数。判断一个数是否为素数的方法有多种，包括试除法、埃筛法等。
暴力法：
素数判定，是检验一个给定的整数是否为素数的测试。
判断 n 是否为素数时，最简单的方式就是暴力法：遍历的所有大于 1 且小于 n 的整数，判断 n 是否可以被这些数整除，如果不存在可以整除的数，则为素数；否则为合数。
#include <bits/stdc++.h>
using namespace std;//暴力法bool isPrime(int n) { if (n <= 1) return false; for (int i = 2; i <= n-1; i++) { if (n % i == 0) { return false; } } return true;
} int main() { int n; cout << "Enter a number: "; cin >> n; if (isPrime(n)) std::cout << n << " is a prime number." << std::endl; else std::cout << n << " is not a prime number." << std::endl; return 0;
}
暴力法的优化：
暴力法效率极低，如果n为一万，则核心代码要跑n-2次，其实我们只需要判断2~√n个数，因为一个数如果可以因数分解（不是质数），那么分解得到的两个数一定是一个小于等于√n，一个大于等于√n，一个合数一定由两个自然数相乘，一个大于等于平方根一个小于等于平方根，并且成对存在，所以只判断前根号个。这时我们需要使用sqrt函数来求根号。
代码如下：
#include <bits/stdc++.h>
using namespace std;//暴力法的优化
bool isPrime(int n) { if (n <= 1) return false; for (int i = 2; i <= sqrt(n); i++) { if (n % i == 0) { return false; } } return true;
} int main() { int n; cout << "Enter a number: "; cin >> n; if (isPrime(n)) std::cout << n << " is a prime number." << std::endl; else std::cout << n << " is not a prime number." << std::endl; return 0;
}
埃式筛选：
埃拉托斯特尼筛法（Sieve of Eratosthenes）是一种简单且古老的用来找出一定范围内所有素数的算法。其基本思想是从2开始，将每个素数的各个倍数，标记为合数（非素数），直到标记到所给定的范围为止。
具体的步骤如下
-
创建一个布尔数组
notPrime[0..n+1]，并初始化为true。这个数组用来表示对应索引的数是否为素数（true表示可能是素数，false表示不是素数或还未检测）。通常notPrime[0]和notPrime[1]会被设为false，因为0和1不是素数。 -
从
p = 2开始，即最小的素数，一直到sqrt(n)（n为要筛的范围）。 -
如果
notPrime[p]为true，则p是一个素数。 -
接下来，标记
p的所有倍数（从p*p开始，一直到n）为非素数。即设置notPrime[p*i]为false，其中i从p开始递增。 -
重复步骤3和4，直到
p超出sqrt(n)。 -
最后，数组中剩余标记为
true的索引对应的数就是素数。
#include <bits/stdc++.h>
using namespace std;//埃式筛法
bool sieveOfEratosthenes(int n,vector<bool>& notPrime) { for (int p = 2; p * p <= n; p++) { //将素数的倍数全部标记为false if (notPrime[p] == true) { for (int i = p * p; i <= n; i += p) notPrime[i] = false; } } return notPrime[n];
}
int main() { int n; cout << "Enter a number: "; cin >> n; vector<bool> notPrime(n + 1, true);notPrime[0] = notPrime[1] = false; if(sieveOfEratosthenes(n,notPrime)) cout << n << " is a prime number." << std::endl; else cout << n << " is not a prime number." << std::endl;return 0;
}欧拉筛选：
具体的步骤如下
埃式筛选任然有一些可以改进的地方，比如说当筛选到2时，会将4,、6、8、10、12等2的倍数标记为false。然而当筛选到3时，会将6、9、12、15等3的倍数标记为fasle，这其中6和12等既是2的倍数又是3的倍数的一些数，会被重复标记。
欧拉筛选素数法是一种更加高效的素数筛选算法，它的基本思想是从2开始，将每个素数的倍数都标记成合数，但与传统的埃拉托斯特尼筛法（Sieve of Eratosthenes）不同，欧拉筛选保证了每个合数只被其最小质因子筛选一次，从而实现了线性的时间复杂度。
下面是欧拉筛选素数法的详细实现步骤：
-
初始化：创建一个布尔数组
isPrime[0..n]，并全部初始化为true。这个数组用于表示从0到n的每个数是否为素数。通常，我们会忽略0和1，因为它们不是素数。 -
筛选过程：
- 从
p = 2开始，这是第一个素数。 - 对于每个
p，遍历所有i（从p的平方开始，直到n），并将isPrime[i*p]设置为false，因为i*p显然不是素数（除非i是1，但这在循环开始条件中已经被排除了）。 - 在遍历
i的过程中，如果发现isPrime[i]已经为false，则跳出内层循环。这是因为如果i不是素数，那么i*p已经被一个比p更小的素数标记过了，无需再次标记。 - 继续增加
p，直到所有小于等于n的数都被检查。
- 从
-
收集素数：最后，遍历
isPrime数组，所有标记为true的位置对应的数就是素数。
这个算法的关键在于，它确保了每个合数只被其最小的质因子筛选一次。这是通过在内层循环中检查 isPrime[i] 并在发现其为 false 时跳出循环来实现的。这样，每个合数只会在其最小质因子第一次出现时被标记，从而避免了重复标记，提高了效率。
欧拉筛选素数法的时间复杂度是线性的，即 O(n)，这使得它在处理大规模数据时比传统的埃拉托斯特尼筛法更加高效。
需要注意的是，虽然欧拉筛选素数法在某些情况下比埃拉托斯特尼筛法更优，但它并不是在所有情况下都是最佳选择。具体使用哪种算法取决于问题的具体要求和数据的规模。
#include <bits/stdc++.h>
using namespace std;
vector<int> primes;
void linearSieve(int n) { vector<bool> isPrime(n + 1, true); for (int i = 2; i <= n; ++i) { if (isPrime[i]) { primes.push_back(i); } for (size_t j = 0; j < primes.size() && i * primes[j] <= n; ++j) { isPrime[i * primes[j]] = false; if (i % primes[j] == 0) { break; } } } } int main() { int n = 100; // 可以根据需要修改这个值 cout << "Prime numbers up to " << n << " are: "; linearSieve(n); for (int prime : primes) { cout << prime << " "; } return 0;
}对于小范围的素数判断，试除法通常足够高效；对于需要生成大量素数的情况，埃筛法更为合适；