P3912 素数个数 · 习题解析｜信息学奥赛算法练功房

0题目原文（本地存了一份）

为什么要在这儿抄一份题面

原题在洛谷上（页头有链接）。别人的网站不归我们管，打不开、改版、题号调整都可能发生。所以每个解析页都把题面转录一份存在本地，跟着仓库一起进版本库。

转录自洛谷 P3912，日期见页头。两边不一致时信原站。

题目描述

求 1, 2, ⋯, N 中素数的个数。

输入格式

一行一个整数 N。

输出格式

一行一个整数，表示素数的个数。

数据范围

对于 40% 的数据，1 ≤ N ≤ 10⁶。
对于 80% 的数据，1 ≤ N ≤ 10⁷。
对于 100% 的数据，1 ≤ N ≤ 10⁸。

时限 2 秒，内存 125 MB（128000 KB）。

输入输出样例

输入

输出

10 以内的素数是 2、3、5、7，一共 4 个。

1第 ① 版：一个一个试除 —— 它值 40 分，而且题面直接告诉你了

p3912Brute.cpp第 ① 版：逐个试除 O(n√n) —— 参照物，稳拿 40 分

// 第 ① 版：一个一个试除判质数 —— 参照物，而且它拿得到 40 分
//
// 题面写着「对于 40% 的数据，1 ≤ N ≤ 10⁶」⇒ 这一版稳拿 40 分。
// ⚠ 顶格 10⁸ 就没戏了：见页面第 1 步那张表。
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    if (scanf("%d", &n) != 1) return 0;
    int ans = 0;
    for (int x = 2; x <= n; x++) {
        bool pr = true;
        for (long long i = 2; i * i <= x; i++) if (x % i == 0) { pr = false; break; }
        if (pr) ans++;
    }
    printf("%d\n", ans);
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

独占实测（3 次取中位数）	耗时	时限 2 秒
`n = 10⁶`（题面 40% 档）	约 165 毫秒	★ 稳拿 40 分
`n = 10⁷`（题面 80% 档）	约 4.2 秒	✗ 超时
`n` 每涨 10 倍，它涨	★ 25.6 倍	（`n√n` 是 31.6 倍）

⇒ 又一次「暴力值多少分」是「暴力 × 那道题分档」的属性：题面把三档写得清清楚楚，乘一遍就知道该写到哪一步。

2第 ② 版：埃氏筛 —— 这一版就已经能过了

p3912.cpp★ 第 ② 版：埃氏筛（内层从 i·i 起），一个 bool 一个数 —— AC

// P3912 素数个数 —— 正解：埃氏筛（内层从 i·i 起），一个 bool 一个数
//
// ★★ 这道题的关卡**不在答案上，在内存和常数上**：n = 10⁸ ⇒
//   · 一个 `bool` 一个数 ⇒ **95.4 MB**，题面给 125 MB（128000 KB）⇒ 过得去（余量 1.31 倍）；
//   · 换成 `int` ⇒ 381.5 MB ⇒ **当场 MLE**（答案一个字不差）；
//   · 换成**线性筛** ⇒ 还要为 5 761 455 个质数留一个 int 数组（22.0 MB）
//     ⇒ 合计 117.4 MB，**余量只剩 1.09 倍**，而且[本章第 10 步](/ch/41-primes/)量过：**它并不更快**。
//
// ⇒ 所以这道题该用的是埃氏筛。⚠ 这不是「线性筛不好」，是**这道题不需要 minp[]**。
#include <bits/stdc++.h>
using namespace std;

static const int MAXN = 100000000;
static bool comp[MAXN + 1];

int main() {
    int n;
    if (scanf("%d", &n) != 1) return 0;
    int ans = 0;
    for (long long i = 2; i * i <= n; i++)
        if (!comp[i]) for (long long j = i * i; j <= n; j += i) comp[j] = true;
    for (int i = 2; i <= n; i++) if (!comp[i]) ans++;
    printf("%d\n", ans);
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

顶格 `n = 10⁸`（独占实测）	实测	题面给	余量
耗时	0.86 秒	2 秒	2.3 倍
内存（表本身 `10⁸ + 1` 个 `bool`）	95.4 MB	125 MB	1.31 倍

⚠ 而内层写 j = 2i 而不是 j = i·i 是答案对但更慢的那一类：划的次数 242 570 204 → 309 275 826，秒表慢 1.84 倍（本章第 5 步证过为什么可以从 i·i 起）。

3★★★ 本章第 10 步那句「线性筛并没有赢」—— 它有一个主语，就是 n

★★★ 同样两种筛，n = 10⁷ 上埃氏筛小赢，n = 10⁸ 上线性筛赢 2.3 倍

第 41 章第 10 步那张表是在 n = 10⁷ 上量的，结论是「线性筛划的次数只有 41%，可它并不更快」。这道题的 n 是 10⁸ —— 把同样四种筛在三个规模上各量一遍（每格 3 次取中位数）：

秒表比值	`n = 10⁷`	`n = 3 × 10⁷`	`n = 10⁸`
埃氏筛(`i·i`) ÷ 线性筛	0.89（埃氏筛小赢）	1.79	★ 2.27（线性筛赢）
埃氏筛(`i·i`) ÷ 奇数＋位压缩	2.30	4.76	★ 5.98

★★★ 第一行跨过了 1 —— 拐点就在 10⁷ 和 3 × 10⁷ 之间。

为什么会翻面：埃氏筛的内层是 j += i，连续地扫过整张表，缓存友好 —— 可它要为每一个质数各扫一遍，一共划 2.43 亿次；而 n = 10⁸ 的那张表有 95 MB，装不进任何一级缓存，于是「扫得连续」这个优势被「反复扫一张放不下的表」吃光了。线性筛每个合数只划一次（0.94 亿次），次数上的优势这时候才兑现成时间。

⇒ ★★ 所以本章那句结论要补一个主语：

「线性筛并不更快」说的是「表还能待在缓存里」的那一段 n。

⇒ 这也是「两把尺子会打架」的又一次，而这一次打完架换了赢家。

p3912Linear.cpp⚠ 线性筛：快 2.27 倍，可它的内存余量只剩 1.09 倍

⚠⚠ 但线性筛在这道题上仍然不该交 —— 它的内存余量只剩 7%

线性筛除了那张 95.4 MB 的表，还得为每个质数留一个 int：

	算出来的字节数	题面给 125 MB ⇒ 余量
埃氏筛（`bool`）	95.4 MB	1.31 倍
⚠ 线性筛（`bool` + `int` 数组）	117.3 MB	★ 1.07 倍
✗ 把 `bool` 换成 `int`	381 MB	✗ MLE
★ 奇数 + 位压缩	★ 6.0 MB	★ 21.0 倍

★ 那个 int 数组要留 π(10⁸) = 5 761 455 格 = 22.0 MB。 ⚠ 本机实测 maxRSS：埃氏筛 99.6 MB、线性筛 121.6 MB —— 离 125 MB 只剩 2.8%。

⇒ ★★ 于是这道题给出一个很别扭但很真实的结论： 跑得快的那一版，是最容易 MLE 的那一版。 而它快出来的那 0.5 秒，在 2 秒的时限里一分钱都不值。

4★ 真正的赢家：把表缩小 —— 又快又省，而且它划得更多

p3912Bit.cpp★ 只存奇数 + 一位一个数 —— 6.0 MB，快 5.98 倍

// ★ 这道题真正的赢家：**只存奇数 ＋ 一位一个数**（位压缩的埃氏筛）
//
// ★★★ 这一页的主角从头到尾是**内存**，不是次数：
//   · 偶数（除了 2）根本不用存 ⇒ 表小一半；
//   · 一个 bool 占 8 位，而我们只要 1 位 ⇒ 再小 8 倍。
//   ⇒ n = 10⁸ 的表从 **95.4 MB 掉到 11.9 MB** —— 小到能长期待在 L2/L3 缓存里。
//
// ⚠ 它划的次数**比线性筛还多**（约 1.15 亿 vs 0.94 亿），秒表却快 2.6 倍
//   ⇒ [两把尺子又打架](/sol/p1074/)，而这一次原因很干净：**表能不能待在缓存里**。
//
// 下标约定：k 代表奇数 2k+1（k = 0 是 1，k = 1 是 3，…）。2 单独算。
#include <bits/stdc++.h>
using namespace std;

static const int MAXN = 100000000;
static uint64_t bs[MAXN / 128 + 2];

static inline bool get(int k) { return (bs[k >> 6] >> (k & 63)) & 1ULL; }
static inline void set1(int k) { bs[k >> 6] |= 1ULL << (k & 63); }

int main() {
    int n;
    if (scanf("%d", &n) != 1) return 0;
    if (n < 2) { puts("0"); return 0; }
    int half = (n - 1) / 2;                          // 3, 5, 7, … 对应 k = 1 … half
    for (long long k = 1; (2 * k + 1) * (2 * k + 1) <= n; k++) {
        if (get((int)k)) continue;
        long long p = 2 * k + 1;
        for (long long j = p * p; j <= n; j += 2 * p) set1((int)((j - 1) / 2));   // 只跳奇数倍
    }
    int ans = 1;                                     // 2 自己
    for (int k = 1; k <= half; k++) if (!get(k)) ans++;
    printf("%d\n", ans);
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

★★★ 它划的次数比线性筛还多，秒表却快 2.63 倍

`n = 10⁸`	划的次数（机器无关）	表的大小	本机耗时
埃氏筛（`i·i` 起）	242 570 204	95.4 MB	0.86 秒
埃氏筛（`2i` 起）	309 275 826	95.4 MB	1.51 秒
线性筛	★ 94 238 544（最少）	117.3 MB	0.37 秒
★ 奇数 + 位压缩	96 285 414（比线性筛多 2.2%）	★ 6.0 MB	★ 0.14 秒

★★★ 最后两行放在一起就是这一页的全部： 次数多 2.2%，时间少 63%。

两步都只是把表缩小： ① 偶数（除了 2）根本不用存 ⇒ 小一半；② 一个 bool 占 8 位而我们只要 1 位 ⇒ 再小 8 倍。 ⇒ 6.0 MB 的表长期待在 L2/L3 里，每一次「跳着写」都不再是一次内存往返。

⇒ ★★ 这道题从头到尾的主角是内存，不是次数 —— 四个版本的答案完全一样，而秒表差 10.8 倍、内存差 64 倍。

5⚠⚠ 五个待测版本里，只有一个的答案是错的

p3912One.cpp✗ 唯一一个真会答错的：把 1 也数成了质数

p3912Slow.cpp⚠ 内层从 2i 起 —— 答案对，只是慢 1.84 倍

p3912Int.cpp⚠ bool 换成 int —— 答案对，381 MB 当场 MLE

p3912Gen.cpp生成器（三档：照题面随机 / 边界 / 顶格）

★★ 对拍在这一页几乎是聋的 —— 它只抓得到一件事

档位（每档 300 轮）	✗ 1 当质数	⚠ 从 `2i` 起	⚠ 线性筛	⚠ `int` 存	★ 位压缩
0 照题面随机（`n ≤ 20000`）	★ 300 / 300	0	0	0	0
1 边界（`n ∈ {1, 2, 3, 4}`）	★ 300 / 300	0	0	0	0

⇒ 五个版本里四个的答案完全正确，它们的差别全在次数和内存上 ⇒ 对拍和官方样例对这四个一点办法都没有，只能数次数 + 算内存。

★ 而那唯一一个答错的，是「每一组都错」型（答案恒多 1） ⇒ 官方样例 n = 10 一测就死（它打 5，答案是 4）—— 又一次「样例是个『一测就死』的过滤器」： 它筛掉的正是最容易被筛掉的那一个。

6★ 哪一版就已经能过了

p3912Count.cpp本页所有数字的出处（四种筛 × 三个规模）

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

// P3912 的度量程序：./p3912Count csv        （本页的数字都出自它）
//
//   marks : ★★ 四种筛各划了多少次（机器无关的那把尺子）。
//   ms    : ★★★ 同样四种筛，在 n = 10⁷ / 3×10⁷ / 10⁸ 三个规模上的秒表 ——
//           **本章第 10 步那句「线性筛并没有赢」的主语是 n**，这张表把拐点找出来了。
//   mem   : ★ 每种写法要多少内存（这是算出来的字节数，不是量出来的 RSS）。
//   pi    : π(10⁸)，也就是那个 int 数组要留多少格。
//
// ⚠ 秒表用 steady_clock 在进程内量，每格跑 3 次取中位数
//   （[第 12 章 P1923 那一跤](/sol/p1923/)：秒表断言的主语是余量，不是量级）。
// ⚠ 报倍数、不报绝对秒数（[硬规矩第 5 条](/ch/41-primes/)）。
#include <bits/stdc++.h>
#include <chrono>
using namespace std;
using namespace std::chrono;

static const int TOP = 100000000;
static bool comp[TOP + 1];
static int prs[5761460];
static uint64_t bs[TOP / 128 + 2];

static inline bool bget(int k) { return (bs[k >> 6] >> (k & 63)) & 1ULL; }
static inline void bset(int k) { bs[k >> 6] |= 1ULL << (k & 63); }

/** ① 埃氏筛，内层从 i·i 起 */
static long long eratSq(int n, long long* marks) {
    memset(comp, 0, (size_t)n + 1);
    long long mk = 0;
    for (long long i = 2; i * i <= n; i++)
        if (!comp[i]) for (long long j = i * i; j <= n; j += i) { comp[j] = true; mk++; }
    long long c = 0;
    for (int i = 2; i <= n; i++) if (!comp[i]) c++;
    if (marks) *marks = mk;
    return c;
}
/** ② 埃氏筛，内层从 2i 起 */
static long long erat2i(int n, long long* marks) {
    memset(comp, 0, (size_t)n + 1);
    long long mk = 0;
    for (long long i = 2; i <= n; i++)
        if (!comp[i]) for (long long j = i + i; j <= n; j += i) { comp[j] = true; mk++; }
    long long c = 0;
    for (int i = 2; i <= n; i++) if (!comp[i]) c++;
    if (marks) *marks = mk;
    return c;
}
/** ③ 线性筛 */
static long long linear(int n, long long* marks) {
    memset(comp, 0, (size_t)n + 1);
    long long mk = 0;
    int cnt = 0;
    for (int i = 2; i <= n; i++) {
        if (!comp[i]) prs[cnt++] = i;
        for (int j = 0; j < cnt && (long long)prs[j] * i <= n; j++) {
            comp[prs[j] * i] = true; mk++;
            if (i % prs[j] == 0) break;
        }
    }
    if (marks) *marks = mk;
    return cnt;
}
/** ④ 只存奇数 + 位压缩的埃氏筛 */
static long long bitSieve(int n, long long* marks) {
    memset(bs, 0, sizeof(uint64_t) * ((size_t)n / 128 + 2));
    if (n < 2) { if (marks) *marks = 0; return 0; }
    long long mk = 0;
    int half = (n - 1) / 2;
    for (long long k = 1; (2 * k + 1) * (2 * k + 1) <= n; k++) {
        if (bget((int)k)) continue;
        long long p = 2 * k + 1;
        for (long long j = p * p; j <= n; j += 2 * p) { bset((int)((j - 1) / 2)); mk++; }
    }
    long long c = 1;
    for (int k = 1; k <= half; k++) if (!bget(k)) c++;
    if (marks) *marks = mk;
    return c;
}

static double med3(double a, double b, double c) { return max(min(a, b), min(max(a, b), c)); }

int main(int argc, char** argv) {
    bool csv = (argc > 1 && string(argv[1]) == "csv");

    const int SIZES[3] = {10000000, 30000000, TOP};
    const char* NAME[4] = {"埃氏筛(i·i 起)", "埃氏筛(2i 起)", "线性筛", "奇数 + 位压缩"};
    long long marks[3][4], ans[3][4];
    double ms[3][4];

    for (int s = 0; s < 3; s++) {
        int n = SIZES[s];
        double t[4][3];
        for (int rep = 0; rep < 3; rep++) {
            for (int k = 0; k < 4; k++) {
                long long mk = 0, a = 0;
                auto t0 = steady_clock::now();
                if (k == 0) a = eratSq(n, &mk);
                else if (k == 1) a = erat2i(n, &mk);
                else if (k == 2) a = linear(n, &mk);
                else a = bitSieve(n, &mk);
                t[k][rep] = duration<double, milli>(steady_clock::now() - t0).count();
                marks[s][k] = mk; ans[s][k] = a;
            }
        }
        for (int k = 0; k < 4; k++) ms[s][k] = med3(t[k][0], t[k][1], t[k][2]);
    }

    /* ⑤ 第 ① 版（逐个试除）：题面 40% 档 / 80% 档各是什么下场 */
    double msBrute6, msBrute7;
    {
        double t[3];
        for (int rep = 0; rep < 3; rep++) {
            auto t0 = steady_clock::now();
            volatile long long c = 0;
            for (int x = 2; x <= 1000000; x++) {
                bool pr = true;
                for (long long i = 2; i * i <= x; i++) if (x % i == 0) { pr = false; break; }
                if (pr) c = c + 1;
            }
            t[rep] = duration<double, milli>(steady_clock::now() - t0).count();
        }
        msBrute6 = med3(t[0], t[1], t[2]);
        auto t0 = steady_clock::now();
        volatile long long c = 0;
        for (int x = 2; x <= 10000000; x++) {
            bool pr = true;
            for (long long i = 2; i * i <= x; i++) if (x % i == 0) { pr = false; break; }
            if (pr) c = c + 1;
        }
        msBrute7 = duration<double, milli>(steady_clock::now() - t0).count();
    }

    long long pi = ans[2][0];
    // 内存（算出来的字节数）
    double memErat = (double)(TOP + 1) / 1048576.0;
    double memLinear = memErat + (double)pi * 4.0 / 1048576.0;
    double memInt = (double)(TOP + 1) * 4.0 / 1048576.0;
    double memBit = (double)(TOP / 128 + 2) * 8.0 / 1048576.0;

    if (csv) {
        printf("pi1e8,%lld\n", pi);
        for (int s = 0; s < 3; s++) {
            bool same = true;
            for (int k = 1; k < 4; k++) if (ans[s][k] != ans[s][0]) same = false;
            printf("same%d,%s\n", s, same ? "1" : "0");
            for (int k = 0; k < 4; k++) printf("marks%d_%d,%lld\n", s, k, marks[s][k]);
            printf("ratLinear%d,%.2f\n", s, ms[s][0] / ms[s][2]);
            printf("ratBit%d,%.2f\n", s, ms[s][0] / ms[s][3]);
            printf("rat2i%d,%.2f\n", s, ms[s][1] / ms[s][0]);
        }
        printf("bitOverLinear,%.2f\n", ms[2][2] / ms[2][3]);
        printf("memErat,%.1f\n", memErat);
        printf("memLinear,%.1f\n", memLinear);
        printf("memInt,%.0f\n", memInt);
        printf("memBit,%.1f\n", memBit);
        printf("headErat,%.2f\n", 125.0 / memErat);
        printf("headLinear,%.2f\n", 125.0 / memLinear);
        printf("headBit,%.2f\n", 125.0 / memBit);
        printf("msBrute1e6,%.0f\n", msBrute6);
        printf("msBrute1e7,%.0f\n", msBrute7);
        printf("bruteGrow,%.1f\n", msBrute7 / msBrute6);
        printf("bruteOverErat1e7,%.1f\n", msBrute7 / ms[0][0]);
        return 0;
    }

    printf("π(10⁸) = %lld\n", pi);
    printf("\n① 划的次数（机器无关）\n");
    printf("   %-18s %14s %14s %14s\n", "n =", "10⁷", "3×10⁷", "10⁸");
    for (int k = 0; k < 4; k++) {
        printf("   %-18s", NAME[k]);
        for (int s = 0; s < 3; s++) printf(" %14lld", marks[s][k]);
        printf("\n");
    }
    printf("\n② 秒表比值（3 次取中位数；★ 只报倍数，绝对秒数写在页面上并注明独占实测）\n");
    printf("   %-24s %10s %10s %10s\n", "", "10⁷", "3×10⁷", "10⁸");
    printf("   %-24s", "埃氏筛(i·i) ÷ 线性筛");
    for (int s = 0; s < 3; s++) printf(" %10.2f", ms[s][0] / ms[s][2]);
    printf("\n   %-24s", "埃氏筛(i·i) ÷ 位压缩");
    for (int s = 0; s < 3; s++) printf(" %10.2f", ms[s][0] / ms[s][3]);
    printf("\n   ⇒ ★★★ 第一行跨过了 1：小 n 上埃氏筛不吃亏，大 n 上线性筛赢\n");
    printf("\n③ 内存（算出来的字节数，不是量出来的 RSS），题面给 125 MB（128000 KB）\n");
    printf("   埃氏筛 bool       %6.1f MB（余量 %.2f 倍）\n", memErat, 125.0 / memErat);
    printf("   线性筛 bool + int %6.1f MB（余量 %.2f 倍）★ 只剩这么点\n", memLinear, 125.0 / memLinear);
    printf("   ✗ 把 bool 换成 int %6.0f MB ⇒ 当场 MLE\n", memInt);
    printf("   ★ 奇数 + 位压缩    %6.1f MB（余量 %.2f 倍）\n", memBit, 125.0 / memBit);
    printf("\n⑤ 第 ① 版（逐个试除）：n = 10⁶ 要 %.0f 毫秒（题面 40%% 档，时限 2 秒 ⇒ **稳拿 40 分**）\n", msBrute6);
    printf("   n = 10⁷ 要 %.0f 毫秒（题面 80%% 档）⇒ ✗ 超时；n 每涨 10 倍它涨 %.1f 倍（n√n 是 31.6 倍）\n",
           msBrute7, msBrute7 / msBrute6);

    printf("\n④ 四种筛在三个规模上的答案是否一致：%s / %s / %s\n",
           ans[0][0] == ans[0][3] ? "是" : "否", ans[1][0] == ans[1][3] ? "是" : "否",
           ans[2][0] == ans[2][3] ? "是" : "否");
    return 0;
}

点一下即可编辑

输出

点「运行 ▶」看结果

第 ② 版（埃氏筛 bool）就能过；后面两版换的是余量

版本	顶格耗时	顶格内存	交上去
① 逐个试除	外推约 130 秒	~0	40 分
★ ② 埃氏筛 `bool`	0.86 秒 / 2 秒	95.4 MB / 125 MB	★ AC
⚠ 线性筛	0.37 秒	117.3 MB（余量 7%）	⚠ 能过，但赌
★ 奇数 + 位压缩	0.14 秒	6.0 MB	★ AC，而且哪一头都不紧

⇒ 题单那句「交之前先想清楚你要用哪一种筛，以及为什么」，答案是： 不是选「哪种筛更聪明」，是先看这道题的 n 让哪张表还待得进缓存、哪张表还塞得进内存。

⚠ 顺带订正一句本书自己的话：题单里写的「本章第 10 步那个实测（线性筛在大 n 上并没有赢）」 —— 那句括号缺了主语。第 10 步量的是 n = 10⁷；到这道题的 n = 10⁸，线性筛是赢的（2.27 倍）。⇒ 题单和本章第 10 步都已按实测改写。

洛谷 P3912 素数个数

0题目原文（本地存了一份）

输入

输出

1第 ① 版：一个一个试除 —— 它值 40 分，而且题面直接告诉你了

2第 ② 版：埃氏筛 —— 这一版就已经能过了

3★★★ 本章第 10 步那句「线性筛并没有赢」—— 它有一个主语，就是 n

4★ 真正的赢家：把表缩小 —— 又快又省，而且它划得更多

5⚠⚠ 五个待测版本里，只有一个的答案是错的

6★ 哪一版就已经能过了