[算法]求n范围以内的质数（素数）的高效算法
质数（prime number）又称素数，是大于1的自然数中除了1和它本身以外不再有其他因数的数。求质数的方法多种多样，其中优化算法是解决大规模质数计算问题的关键。
暴力法
暴力法是最简单也是最直观的质数求解方法，尽管效率不高，但在某些特殊场景下仍然适用。
代码示例：
void prime() {
int N = 10000;
int primes[N], pos = 0;
register int i, j;
for (i = 2; i < N; i++) {
bool flag = 0;
for (j = 2; j < i; j++) {
if (i % j == 0) {
flag = 1;
break;
}
}
if (flag == 0) {
primes[++pos] = i;
}
}
}
这种方法的时间复杂度为O(N²)，在N较大的情况下效率较低。
埃拉托斯特尼筛法
埃拉托斯特尼筛法是一种高效的质数筛选算法，通过逐步排除非质数来实现。其时间复杂度为O(N log log N)。
代码示例：
void prime() {
int N = 10000;
register int i, j;
bool prim[N];
memset(prim, 0, sizeof(prim));
prim[1] = 1;
for (i = 2; i <= sqrt(N); i++) {
if (prim[i] == 0) {
for (j = i + i; j <= N; j += i) {
prim[j] = 1;
}
}
}
}
该算法通过标记非质数来实现筛选，避免了重复计算，效率较高。
欧拉筛选法
欧拉筛选法是一种进一步优化的筛法，其时间复杂度为O(N)。该算法通过确保每个合数只被最小质因子筛选一次，从而避免了冗余计算。
代码示例：
void prime() {
int N = 10000;
int prim[N], bz[N], top = 0;
memset(bz, 0, sizeof(bz));
register int i, j;
for (i = 2; i <= N; i++) {
if (!bz[i]) {
prim[++top] = i;
}
for (j = 0; j <= top && i * prim[j] <= N; j++) {
bz[i * prim[j]] = 1;
if (i % prim[j] == 0) {
break;
}
}
}
}
与埃拉托斯特尼筛法相比，欧拉筛选法在处理质数倍数时更加高效，减少了重复计算的次数。
尽管上述方法在不同场景下有不同的性能表现，但在实际应用中，选择合适的算法是关键。对于大规模的数据处理，建议采用欧拉筛选法或埃拉托斯特尼筛法，以获得更好的性能。
