洛谷 P3383 【模板】线性筛素数

// 第 ① 版：不筛 —— 每个询问都从 2 开始一个一个试除，数到第 k 个为止
//
// 这是「还没想到筛」的人真实的第一反应，也是本页的参照物。
// ⚠ 顶格 n = 10⁸、q = 10⁶：光第一问就可能要数到第 5 761 455 个素数 ⇒ 想都不用想。
#include <bits/stdc++.h>
using namespace std;

static bool isPrime(int x) {
    if (x < 2) return false;
    if (x % 2 == 0) return x == 2;
    for (int i = 3; (long long)i * i <= x; i += 2) if (x % i == 0) return false;
    return true;
}

int main() {
    int n, q;
    if (scanf("%d %d", &n, &q) != 2) return 0;
    for (int i = 0; i < q; i++) {
        int k;
        if (scanf("%d", &k) != 1) break;
        int c = 0, x = 1;
        while (c < k) { x++; if (isPrime(x)) c++; }
        printf("%d\n", x);
    }
    return 0;
}

// P3383【模板】线性筛素数 —— 正解：线性筛把素数表存下来，第 k 小 O(1) 回答
//
// ★★ 这道题和同章的 [P3912](/sol/p3912/) 是一对，而**结论相反**：
//   那道题只要「有几个」⇒ 表可以压成位、素数一个都不用存；
//   这道题要「第 k 小是谁」⇒ **必须把素数按序存下来** ⇒ 那个 int 数组躲不掉。
//   ⚠ 而这道题的内存限制是 **512 MB**（那道题只有 125）—— 所以这里根本不用为内存操心。
//
// ★ 那句 break 保证的是「每个合数只被它的**最小**质因子划掉一次」（[本章第 6 步](/ch/41-primes/)）。
//
// ⚠⚠ 真正会挂人的是 I/O：q 可以到 10⁶ ⇒ 读 8 MB、写 10 MB。
//   题面自己写着「建议 sync_with_stdio(0)，并且用 '\n' 换行」——
//   这一页把那句话量了一遍（见 p3383Io.cpp）。
#include <bits/stdc++.h>
using namespace std;

static const int MAXN = 100000000;
static bool comp[MAXN + 1];
static int pr[5761460];
static int cnt = 0;

static char ibuf[1 << 22];
static size_t ilen = 0, ipos = 0;
static inline int gc() {
    if (ipos == ilen) { ilen = fread(ibuf, 1, sizeof(ibuf), stdin); ipos = 0; if (!ilen) return -1; }
    return ibuf[ipos++];
}
static inline int readInt() {
    int c = gc();
    while (c != -1 && (c < '0' || c > '9')) c = gc();
    int v = 0;
    while (c >= '0' && c <= '9') { v = v * 10 + (c - '0'); c = gc(); }
    return v;
}
static char obuf[1 << 22];
static size_t opos = 0;
/** ⚠ 缓冲区写满就先吐出去 —— 顶格输出约 10 MB，一次性攒在数组里会溢出
 *  （[第 12 章那一跤](/sol/p1226/)的输出侧版本：缓冲区开小了会一声不吭地出事）。 */
static inline void flushOut() { fwrite(obuf, 1, opos, stdout); opos = 0; }
static inline void writeInt(int x) {
    if (opos + 16 > sizeof(obuf)) flushOut();
    char t[12]; int m = 0;
    if (!x) t[m++] = '0';
    while (x) { t[m++] = char('0' + x % 10); x /= 10; }
    while (m) obuf[opos++] = t[--m];
    obuf[opos++] = '\n';
}

int main() {
    int n = readInt(), q = readInt();
    for (int i = 2; i <= n; i++) {
        if (!comp[i]) pr[cnt++] = i;
        for (int j = 0; j < cnt && (long long)pr[j] * i <= n; j++) {
            comp[pr[j] * i] = true;
            if (i % pr[j] == 0) break;          // ★ 这一句就是「线性」的全部
        }
    }
    for (int i = 0; i < q; i++) {
        int k = readInt();
        writeInt(pr[k - 1]);                     // ⚠ 第 k 小 ⇒ 下标 k−1
    }
    flushOut();
    return 0;
}

// ★ 再快一点：先用「只存奇数 + 一位一个数」的埃氏筛，再把素数提取成表
//
// ★★ 这是 [P3912](/sol/p3912/) 那条结论在这道题上的延伸：
//   筛那一步的主角是**表能不能待在缓存里** —— 6.0 MB 的位表比 95.4 MB 的 bool 表快得多。
// ⚠ 但这道题**躲不掉那个 int 素数表**（要回答「第 k 小」）⇒ 内存还是 22 MB 起步，
//   只是题面给了 512 MB，一点不紧。
#include <bits/stdc++.h>
using namespace std;

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

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); }

static char ibuf[1 << 22];
static size_t ilen = 0, ipos = 0;
static inline int gc() {
    if (ipos == ilen) { ilen = fread(ibuf, 1, sizeof(ibuf), stdin); ipos = 0; if (!ilen) return -1; }
    return ibuf[ipos++];
}
static inline int readInt() {
    int c = gc();
    while (c != -1 && (c < '0' || c > '9')) c = gc();
    int v = 0;
    while (c >= '0' && c <= '9') { v = v * 10 + (c - '0'); c = gc(); }
    return v;
}
static char obuf[1 << 22];
static size_t opos = 0;
/** ⚠ 缓冲区写满就先吐出去 —— 顶格输出约 10 MB，一次性攒在数组里会溢出
 *  （[第 12 章那一跤](/sol/p1226/)的输出侧版本：缓冲区开小了会一声不吭地出事）。 */
static inline void flushOut() { fwrite(obuf, 1, opos, stdout); opos = 0; }
static inline void writeInt(int x) {
    if (opos + 16 > sizeof(obuf)) flushOut();
    char t[12]; int m = 0;
    if (!x) t[m++] = '0';
    while (x) { t[m++] = char('0' + x % 10); x /= 10; }
    while (m) obuf[opos++] = t[--m];
    obuf[opos++] = '\n';
}

int main() {
    int n = readInt(), q = readInt();
    int cnt = 0;
    if (n >= 2) {
        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));
        }
        pr[cnt++] = 2;
        for (int k = 1; k <= half; k++) if (!bget(k)) pr[cnt++] = 2 * k + 1;
    }
    for (int i = 0; i < q; i++) { int k = readInt(); writeInt(pr[k - 1]); }
    flushOut();
    return 0;
}

// P3383 的 I/O 账：./p3383Io [csv]
//
// ⚠⚠ **题面自己点名了这件事**：「本题输入输出、运算数据量较大 …… 如果你使用 cin 来输入输出，
//   建议使用 std::ios::sync_with_stdio(0) 来加速，同时使用 '\n' 换行输出。」
//   ⇒ 而[流传很广的提醒量完之后要打个折](/sol/p1972/) —— 这一份就是那把秤。
//
// 顶格形状：q = 10⁶ 个询问 ⇒ **读约 7.8 MB、写约 10 MB**（答案最大 9 位数）。
//
// 四种读法 × 五种写法，各跑 3 次取中位数。
// ⚠ 顺序不能换：① 「同步开着」的两种写法和「默认 cin」必须排在关同步**之前**
//   （关掉同步之后 cin/cout 会自己缓冲，之后的测量就不是那回事了）；
//   ② 关同步之后 cin 会预读一大块，freopen 换文件时缓冲里是上一份的残渣
//   （第 45 章 read.cpp、第 6 章 p2367Read.cpp、第 35 章 p5788Io.cpp、第 37 章 p3378Io.cpp 都踩过）。
//
// ★ 报的是**绝对毫秒数**（时限 3000 ms）—— [倍数跨题几乎不变，而「够不够」比的是绝对时间](/sol/p1972/)。
#include <bits/stdc++.h>
#include <chrono>
#include <unistd.h>
#include <fcntl.h>
using namespace std;
using namespace std::chrono;

static const int Q = 1000000;
static char inPath[64], outPath[64];
static vector<int> ks, vals;

static void makeData() {
    snprintf(inPath, sizeof(inPath), "/tmp/p3383-in-%d.txt", (int)getpid());
    snprintf(outPath, sizeof(outPath), "/tmp/p3383-out-%d.txt", (int)getpid());
    mt19937 rng(20260902u);
    ks.resize(Q); vals.resize(Q);
    FILE* fp = fopen(inPath, "w");
    if (!fp) { fprintf(stderr, "写不出临时文件\n"); exit(1); }
    fprintf(fp, "%d %d\n", 100000000, Q);
    for (int i = 0; i < Q; i++) {
        unsigned k = 1u + (unsigned)(rng() % 5761455u);       // ⚠ 先落到具名变量再传参
        ks[i] = (int)k;
        unsigned v = 2u + (unsigned)(rng() % 99999998u);      // 冒充「第 k 小的素数」，位数一致
        vals[i] = (int)v;
        fprintf(fp, "%u\n", k);
    }
    fclose(fp);
}
static void reopenIn() { if (!freopen(inPath, "r", stdin)) { fprintf(stderr, "读不回\n"); exit(1); } }
/* ⚠ 输出重定向用 dup2 而不是 freopen：freopen 回不来
 *    （这台机器上没有 /dev/tty，第一版就把本程序自己的报告写丢了）。 */
static int savedOut = -1;
static void reopenOut() {
    fflush(stdout);
    int fd = open(outPath, O_WRONLY | O_CREAT | O_TRUNC, 0644);
    if (fd < 0) { fprintf(stderr, "写不出\n"); exit(1); }
    if (dup2(fd, 1) < 0) { fprintf(stderr, "dup2 失败\n"); exit(1); }
    close(fd);
}
static void backOut() { fflush(stdout); if (dup2(savedOut, 1) < 0) exit(1); }

/* ---------------- 读 ---------------- */
static long long readCin(long long& sum) {
    reopenIn();
    auto t0 = steady_clock::now();
    int n, q; cin >> n >> q; sum = n;
    for (int i = 0; i < q; i++) { int k; cin >> k; sum += k; }
    return duration_cast<milliseconds>(steady_clock::now() - t0).count();
}
static long long readNosync(long long& sum) {
    reopenIn();
    ios::sync_with_stdio(false); cin.tie(nullptr);
    auto t0 = steady_clock::now();
    int n, q; cin >> n >> q; sum = n;
    for (int i = 0; i < q; i++) { int k; cin >> k; sum += k; }
    return duration_cast<milliseconds>(steady_clock::now() - t0).count();
}
static long long readScanf(long long& sum) {
    reopenIn();
    auto t0 = steady_clock::now();
    int n, q;
    if (scanf("%d %d", &n, &q) != 2) exit(1);
    sum = n;
    for (int i = 0; i < q; i++) { int k; if (scanf("%d", &k) != 1) exit(1); sum += k; }
    return duration_cast<milliseconds>(steady_clock::now() - t0).count();
}
static char ibuf[1 << 22];
static size_t ilen = 0, ipos = 0;
static inline int gc() {
    if (ipos == ilen) { ilen = fread(ibuf, 1, sizeof(ibuf), stdin); ipos = 0; if (!ilen) return -1; }
    return ibuf[ipos++];
}
static inline int readInt() {
    int c = gc();
    while (c != -1 && (c < '0' || c > '9')) c = gc();
    int v = 0;
    while (c >= '0' && c <= '9') { v = v * 10 + (c - '0'); c = gc(); }
    return v;
}
static long long readFast(long long& sum) {
    reopenIn(); ilen = ipos = 0;
    auto t0 = steady_clock::now();
    int n = readInt(), q = readInt(); sum = n;
    for (int i = 0; i < q; i++) sum += readInt();
    return duration_cast<milliseconds>(steady_clock::now() - t0).count();
}

/* ---------------- 写 ---------------- */
static long long writeEndl() {
    reopenOut();
    auto t0 = steady_clock::now();
    for (int i = 0; i < Q; i++) cout << vals[i] << endl;
    cout.flush();
    long long ms = duration_cast<milliseconds>(steady_clock::now() - t0).count();
    backOut(); return ms;
}
static long long writeNl() {
    reopenOut();
    auto t0 = steady_clock::now();
    for (int i = 0; i < Q; i++) cout << vals[i] << '\n';
    cout.flush();
    long long ms = duration_cast<milliseconds>(steady_clock::now() - t0).count();
    backOut(); return ms;
}
static long long writeNlNosync() {
    reopenOut();
    auto t0 = steady_clock::now();
    for (int i = 0; i < Q; i++) cout << vals[i] << '\n';
    cout.flush();
    long long ms = duration_cast<milliseconds>(steady_clock::now() - t0).count();
    backOut(); return ms;
}
static long long writePrintf() {
    reopenOut();
    auto t0 = steady_clock::now();
    for (int i = 0; i < Q; i++) printf("%d\n", vals[i]);
    fflush(stdout);
    long long ms = duration_cast<milliseconds>(steady_clock::now() - t0).count();
    backOut(); return ms;
}
static char obuf[1 << 22];
static size_t opos = 0;
static inline void flushOut() { fwrite(obuf, 1, opos, stdout); opos = 0; }
static inline void putInt(int x) {
    if (opos + 16 > sizeof(obuf)) flushOut();
    char t[12]; int m = 0;
    if (!x) t[m++] = '0';
    while (x) { t[m++] = char('0' + x % 10); x /= 10; }
    while (m) obuf[opos++] = t[--m];
    obuf[opos++] = '\n';
}
static long long writeFwrite() {
    reopenOut(); opos = 0;
    auto t0 = steady_clock::now();
    for (int i = 0; i < Q; i++) putInt(vals[i]);
    flushOut(); fflush(stdout);
    long long ms = duration_cast<milliseconds>(steady_clock::now() - t0).count();
    backOut(); return ms;
}

static long long med3(long long a, long long b, long long 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";
    savedOut = dup(1);
    if (savedOut < 0) return 1;
    makeData();
    long long inBytes = 0, outBytes = 0;
    { FILE* f = fopen(inPath, "rb"); fseek(f, 0, SEEK_END); inBytes = ftell(f); fclose(f); }

    /* ⚠ 顺序：同步开着的两种写法 + 默认 cin 必须排在关同步之前 */
    long long wEndl = med3(writeEndl(), writeEndl(), writeEndl());
    { FILE* f = fopen(outPath, "rb"); fseek(f, 0, SEEK_END); outBytes = ftell(f); fclose(f); }
    long long wNl = med3(writeNl(), writeNl(), writeNl());
    long long s1, s2, s3, s4;
    long long rCin = med3(readCin(s1), readCin(s1), readCin(s1));
    long long rNos = med3(readNosync(s2), readNosync(s2), readNosync(s2));
    long long wNlNos = med3(writeNlNosync(), writeNlNosync(), writeNlNosync());
    long long rScan = med3(readScanf(s3), readScanf(s3), readScanf(s3));
    long long wPrt = med3(writePrintf(), writePrintf(), writePrintf());
    long long rFast = med3(readFast(s4), readFast(s4), readFast(s4));
    long long wFwr = med3(writeFwrite(), writeFwrite(), writeFwrite());
    int same = (s1 == s2 && s2 == s3 && s3 == s4);
    remove(inPath); remove(outPath);

    if (csv) {
        printf("inBytes,%lld\n", inBytes);
        printf("outBytes,%lld\n", outBytes);
        printf("rCin,%lld\n", rCin);
        printf("rNosync,%lld\n", rNos);
        printf("rScanf,%lld\n", rScan);
        printf("rFast,%lld\n", rFast);
        printf("wEndl,%lld\n", wEndl);
        printf("wNl,%lld\n", wNl);
        printf("wNlNosync,%lld\n", wNlNos);
        printf("wPrintf,%lld\n", wPrt);
        printf("wFwrite,%lld\n", wFwr);
        printf("same,%d\n", same);
        printf("worstIo,%lld\n", rCin + wEndl);
        printf("bestIo,%lld\n", rFast + wFwr);
        return 0;
    }
    printf("顶格 q = 10⁶：输入 %lld 字节（%.1f MB），输出 %lld 字节（%.1f MB）\n",
           inBytes, inBytes / 1048576.0, outBytes, outBytes / 1048576.0);
    printf("\n读（3 次取中位数，时限 3000 ms）\n");
    printf("  默认 cin %lld ms ／ 关同步 cin %lld ms ／ scanf %lld ms ／ fread 快读 %lld ms\n",
           rCin, rNos, rScan, rFast);
    printf("  四种读法校验和一致：%s\n", same ? "是" : "否");
    printf("\n写（3 次取中位数）\n");
    printf("  cout << endl %lld ms ／ cout << '\\n' %lld ms ／ 关同步 + '\\n' %lld ms ／ printf %lld ms ／ fwrite %lld ms\n",
           wEndl, wNl, wNlNos, wPrt, wFwr);
    printf("\n⇒ 最差的一套（默认 cin + endl）合计 %lld ms，最好的一套（快读 + fwrite）合计 %lld ms\n",
           rCin + wEndl, rFast + wFwr);
    return 0;
}

// P3383 的度量程序：./p3383Count csv        （本页筛那一半的数字出自它）
//
//   marks : 四种筛在 n = 10⁸ 上各划了多少次（机器无关的那把尺子）。
//   ms    : 同样四种，2 次取较小值（★ 只报倍数，绝对秒数在页面上注明独占实测）。
//   mem   : ★ 这道题**躲不掉那个 int 素数表**（要回答「第 k 小」）—— 算一遍它多大。
//
// ⚠ 和 [P3912](/sol/p3912/) 那一页的对照：那道题只要「有几个」⇒ 素数一个都不用存、
//   表还能压成位；这道题要「第 k 小是谁」⇒ 表躲不掉。**同一章，两个相反的结论。**
#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); }

/** ① 线性筛 + 素数表 */
static int linear(int n, long long& mk) {
    memset(comp, 0, (size_t)n + 1); 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;
        }
    }
    return cnt;
}
/** ② 忘了那句 break */
static int noBreak(int n, long long& mk) {
    memset(comp, 0, (size_t)n + 1); 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++; }
    }
    return cnt;
}
/** ③ 埃氏筛（i·i 起）+ 收集 */
static int eratCollect(int n, long long& mk) {
    memset(comp, 0, (size_t)n + 1); 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++; }
    int cnt = 0;
    for (int i = 2; i <= n; i++) if (!comp[i]) prs[cnt++] = i;
    return cnt;
}
/** ④ 只存奇数 + 位压缩，再提取素数表 */
static int bitCollect(int n, long long& mk) {
    memset(bs, 0, sizeof(uint64_t) * ((size_t)n / 128 + 2)); mk = 0;
    int half = (n - 1) / 2, cnt = 0;
    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++; }
    }
    prs[cnt++] = 2;
    for (int k = 1; k <= half; k++) if (!bget(k)) prs[cnt++] = 2 * k + 1;
    return cnt;
}

int main(int argc, char** argv) {
    bool csv = (argc > 1 && string(argv[1]) == "csv");
    const char* NAME[4] = {"线性筛", "忘了 break", "埃氏筛(i·i)+收集", "奇数位压缩+提取"};
    long long mk[4] = {0, 0, 0, 0};
    int cnt[4] = {0, 0, 0, 0};
    double ms[4] = {0, 0, 0, 0};
    for (int rep = 0; rep < 2; rep++)
        for (int k = 0; k < 4; k++) {
            long long m = 0;
            auto t0 = steady_clock::now();
            int c = (k == 0) ? linear(TOP, m) : (k == 1) ? noBreak(TOP, m)
                  : (k == 2) ? eratCollect(TOP, m) : bitCollect(TOP, m);
            double t = duration<double, milli>(steady_clock::now() - t0).count();
            if (rep == 0 || t < ms[k]) ms[k] = t;
            mk[k] = m; cnt[k] = c;
        }

    bool same = (cnt[0] == cnt[1] && cnt[1] == cnt[2] && cnt[2] == cnt[3]);
    double memTable = (double)cnt[0] * 4.0 / 1048576.0;      // int 素数表
    double memBool = (double)(TOP + 1) / 1048576.0;
    double memBit = (double)(TOP / 128 + 2) * 8.0 / 1048576.0;

    if (csv) {
        printf("pi,%d\n", cnt[0]);
        printf("same,%d\n", same ? 1 : 0);
        for (int k = 0; k < 4; k++) printf("marks%d,%lld\n", k, mk[k]);
        printf("ratNoBreak,%.2f\n", ms[1] / ms[0]);
        printf("ratErat,%.2f\n", ms[2] / ms[0]);
        printf("ratBit,%.2f\n", ms[0] / ms[3]);
        printf("memTable,%.1f\n", memTable);
        printf("memLinear,%.1f\n", memBool + memTable);
        printf("memBit,%.1f\n", memBit + memTable);
        printf("headLinear,%.1f\n", 512.0 / (memBool + memTable));
        return 0;
    }
    printf("π(10⁸) = %d，四种筛数出来的个数一致：%s\n", cnt[0], same ? "是" : "否");
    printf("\n① 划的次数（机器无关）\n");
    for (int k = 0; k < 4; k++) printf("   %-20s %14lld\n", NAME[k], mk[k]);
    printf("\n② 秒表比值（2 次取较小值）\n");
    printf("   忘了 break ÷ 线性筛      = %.2f\n", ms[1] / ms[0]);
    printf("   埃氏筛+收集 ÷ 线性筛     = %.2f\n", ms[2] / ms[0]);
    printf("   线性筛 ÷ 位压缩+提取     = %.2f\n", ms[0] / ms[3]);
    printf("\n③ 内存（算出来的字节数），题面给 **512 MB**\n");
    printf("   素数表本身（%d 个 int）      %6.1f MB ← ⚠ 这道题躲不掉它\n", cnt[0], memTable);
    printf("   线性筛（bool 表 + 素数表）    %6.1f MB（余量 %.1f 倍）\n", memBool + memTable, 512.0 / (memBool + memTable));
    printf("   位压缩（位表 + 素数表）       %6.1f MB\n", memBit + memTable);
    return 0;
}