公告

输出 1e5+7 以内的所有素数：

#include <iostream>
#include <ctime>
using namespace std;
const int N = 1e5 + 7;
bool isP(int x) {
    if (x<2 || (x>2 && x%2==0)) return false;
    for (int i = 3; i*i <= x; i += 2)
        if (x % i == 0) return false;
    return true;
}
int main() {
    clock_t start, end;
    start = clock();
    for (int i = 2; i < N; ++i)
        if (isP(i)) printf("%d ", i);
    end = clock();
    printf("time: %d\n", end-start);
}

埃氏筛

---

除了能够检验给定整数 𝑥 是否为素数的函数之外，如果能够事先准备好素数表就可以帮助我们更有效地求解素数的相关问题。埃拉托色尼筛选法（Sieve of Eratosthenes）可以快速列举出给定范围内的所有素数。

 #include <iostream>
    #include <ctime>
    using namespace std;
    const int N = 1e5 + 7;
    int pr[N/5], ct;
    bool isP[N];// true表示不是素数
    int main() {
        clock_t start, end;
        start = clock();
        isP[1] = true;
        for (int i = 2; i < N; ++i) {
            if (isP[i]) continue;
            pr[++ct] = i;
            for (int j = i+i; j < N; j += i)
                isP[j] = true;
        }
        end = clock();
        printf("time: %d\n", end-start);
    }

欧拉筛(线性筛)

---

埃氏筛有一个缺点，每个数会被筛多次。

可以考虑将每个数都只用它最小的质因数筛掉，例如：8 被 2×4 筛掉，27 被 3×9 筛掉，……。

由此我们设计出欧拉筛的算法：用每个数 x（不论是否是素数）从最小的质数开始逐一相乘，将乘积得数筛去，直到该素数为 x 的最小质因数为止。

#include <iostream> 
#include <ctime> 
using namespace std; 
const int N = 1e5 + 7;
 int pr[N/5], ct; 
isP[N];// true表示不是素数 
int main() { clock_t start, end; start = clock(); isP[1] = true; for (int i = 2; i < N; ++i) { if (!isP[i]) pr[++ct] = i; for (int j = 1; j<=ct && 1LL*pr[j]*i<N; ++j) { isP[pr[j]*i] = true; if (i%pr[j] == 0) break; } } end = clock(); printf("time: %d\n", end-start); }

---

转载请注明来源