洛谷 P1075 [NOIP 2012 普及组] 质因数分解

// ✗ 第 ① 版：照定义硬做 —— 枚举 2..n，是因子又是质数就更新最大值
//
// 这是绝大多数人真实的第一反应：题目问「较大的那个质数」，那就把所有质因子都找出来取最大。
// 它是对的，也是本页的**参照物**；但复杂度是 O(n√n)，顶格 n = 2×10⁹ 想都不用想。
#include <bits/stdc++.h>
using namespace std;

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

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

// P1075 质因数分解 —— 正解：试除到 √n，答案 = n / 最小质因子
//
// ★ 两句话就是全部：
//   ① n = p·q（p < q 都是质数）⇒ **较小的那个 p ≤ √n**（不然 p·q > n）；
//   ② 从 2 往上数，**碰到的第一个因子一定是质数** ——
//      它若有更小的因子 d，那 d 也整除 n，就轮不到它当「第一个」了。
//   ⇒ 于是根本不用判质数，找到第一个因子就停，输出 n / 它。
//
// ⚠ 循环上界写 i * i <= n：顶格 n = 2×10⁹ 时 i 最大到 44721，
//   i * i 最大约 2×10⁹ < 2³¹−1 = 2 147 483 647 ⇒ int **恰好够，余量 7.4%**
//   （p1075Count.cpp 把这个数算出来了）。
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    if (scanf("%d", &n) != 1) return 0;
    for (int i = 2; (long long)i * i <= n; i++)
        if (n % i == 0) { printf("%d\n", n / i); return 0; }
    printf("%d\n", n);   // 题面保证不会走到这里（n 一定是两个质数之积）
    return 0;
}

// P1075 的度量程序：./p1075Count csv        （本页的数字都出自它）
//
//   exh   : ★★ 全范围穷举 —— n ≤ 10⁷ 的**全部**「两个不同质数之积」，
//           拿一条完全无关的路（线性筛出来的最小质因子表）逐个核对正解。
//   same  : ★★★ 「循环上界写 i <= n」和「写 i * i <= n」**试除次数逐个相同** ——
//           因为最小质因子必 ≤ √n，循环总在那儿停 ⇒ **上界写多大在这道题上是免费的**。
//   int   : ★ 「i * i 会不会撑破 int」是一道算术题：答案是**恰好够**，余量多少。
//   steps : ★ 正解最坏走多少次 ↔ 「不 break 扫到底」走多少次。
//   ms    : 秒表（正解跑一万次取平均；不 break 那版在 n = 2×10⁸ 上量一次再外推顶格）。
//   sieve : ⚠ 「那就筛」要多少内存。
//   dens  : ⚠ 顺手随机一个 n，有多大概率真是「两个不同质数之积」——
//           这道题的生成器**必须**照题面反着造。
//
// ⚠ 秒表用 steady_clock 在进程内量（[第 35 章那一跤](/sol/p2866/)：别拿 shell 的时间戳相减）。
#include <bits/stdc++.h>
#include <chrono>
using namespace std;
using namespace std::chrono;

static const int EXH = 10000000;              // 10⁷
static const long long NMAX = 2000000000LL;   // 题面上界

/** 正解：试除到 √n，返回答案；trials 带回试除了几次 */
static int solve(int n, long long& trials) {
    trials = 0;
    for (int i = 2; (long long)i * i <= n; i++) {
        trials++;
        if (n % i == 0) return n / i;
    }
    return n;
}
/** 上界写 i <= n 的版本（同样 break）：只数次数 */
static long long trialsLoose(int n) {
    long long t = 0;
    for (int i = 2; i <= n; i++) { t++; if (n % i == 0) break; }
    return t;
}

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

    /* ① 线性筛出 [2, 10⁷] 的最小质因子 —— 这是「完全无关的另一条路」 */
    vector<int> minp(EXH + 1, 0);
    vector<int> pr;
    pr.reserve(700000);
    for (int i = 2; i <= EXH; i++) {
        if (!minp[i]) { minp[i] = i; pr.push_back(i); }
        for (int p : pr) {
            if ((long long)p * i > EXH || p > minp[i]) break;
            minp[(long long)p * i] = p;
        }
    }

    /* ② 全范围穷举：所有 n = p·q（p < q 都是质数）*/
    long long exhTotal = 0, exhMismatch = 0, sameDiff = 0, semiAll = 0;
    for (int n = 4; n <= EXH; n++) {
        int p = minp[n];
        int m = n / p;
        if (minp[m] != m) continue;           // m 不是质数 ⇒ n 不是两个质数之积
        semiAll++;
        if (p == m) continue;                 // 题面要「两个**不同**的质数」
        exhTotal++;
        long long tr = 0;
        if (solve(n, tr) != m) exhMismatch++;
        if (n <= 200000 && trialsLoose(n) != tr) sameDiff++;   // 次数对照只跑前一段（够说明问题）
    }

    /* ③ 「i * i 撑不撑得破 int」：找出最大的、能出现在题面里的最小质因子 */
    long long maxP = 0, maxQ = 0;
    {
        // p 是较小的那个 ⇒ p ≤ √(2×10⁹)；要求存在质数 q > p 使 p·q ≤ 2×10⁹
        int lim = 44730;
        vector<char> comp(lim + 1, 0);
        vector<int> sp;
        for (int i = 2; i <= lim; i++) {
            if (!comp[i]) sp.push_back(i);
            for (long long j = (long long)i * i; j <= lim; j += i) comp[j] = 1;
        }
        for (size_t i = 0; i + 1 < sp.size(); i++) {
            long long p = sp[i], q = sp[i + 1];
            if (p * q <= NMAX) { maxP = p; maxQ = q; }
        }
    }
    long long maxSq = maxP * maxP;
    long long INT_TOP = 2147483647LL;

    /* ④ 秒表 */
    int topN = (int)(maxP * maxQ);
    double usFast = 0;
    {
        auto t0 = steady_clock::now();
        volatile long long acc = 0;
        long long tr = 0;
        for (int r = 0; r < 10000; r++) acc = acc + solve(topN, tr);
        auto t1 = steady_clock::now();
        usFast = duration<double, micro>(t1 - t0).count() / 10000.0;
    }
    double msNoBreak = 0;
    {
        const int probe = 200000000;          // 2×10⁸，再外推到顶格
        auto t0 = steady_clock::now();
        volatile int ans = probe;
        for (int i = 2; i < probe; i++) if (probe % i == 0) ans = i;
        (void)ans;
        auto t1 = steady_clock::now();
        msNoBreak = duration<double, milli>(t1 - t0).count();
    }
    double projNoBreakSec = msNoBreak / 1000.0 * (double)NMAX / 200000000.0;

    /* ⑤ 「那就筛」要多少内存 */
    double sieveMB = (double)NMAX / 1048576.0;      // 一个字节一个数
    double limitMB = 128.0;

    if (csv) {
        printf("exhTotal,%lld\n", exhTotal);
        printf("exhMismatch,%lld\n", exhMismatch);
        printf("semiAll,%lld\n", semiAll);
        printf("sameDiff,%lld\n", sameDiff);
        printf("maxP,%lld\n", maxP);
        printf("maxQ,%lld\n", maxQ);
        printf("maxSq,%lld\n", maxSq);
        printf("intTop,%lld\n", INT_TOP);
        printf("marginPct,%.1f\n", (double)(INT_TOP - maxSq) * 100.0 / (double)maxSq);
        printf("worstTrial,%lld\n", maxP - 1);
        printf("noBreakSteps,%lld\n", NMAX - 2);
        printf("stepRatio,%.0f\n", (double)(NMAX - 2) / (double)(maxP - 1));
        printf("usFast,%.3f\n", usFast);
        printf("msNoBreak2e8,%.0f\n", msNoBreak);
        printf("projNoBreakSec,%.1f\n", projNoBreakSec);
        printf("sieveMB,%.0f\n", sieveMB);
        printf("sieveRatio,%.1f\n", sieveMB / limitMB);
        printf("densPct,%.1f\n", (double)exhTotal * 100.0 / (double)EXH);
        return 0;
    }

    printf("① 全范围穷举（n ≤ 10⁷ 的全部「两个不同质数之积」）\n");
    printf("   这样的 n 一共 %lld 个（占 %.1f%%）；正解和「线性筛的最小质因子表」不一致 %lld 组\n",
           exhTotal, (double)exhTotal * 100.0 / EXH, exhMismatch);
    printf("   ⚠ 顺手随机一个 n，只有 %.1f%% 真的是题面说的那种 ⇒ 生成器必须反着造\n",
           (double)exhTotal * 100.0 / EXH);
    printf("\n② 上界写 i <= n ↔ 写 i*i <= n：试除次数不同的组数 = %lld\n", sameDiff);
    printf("   ⇒ 最小质因子必 ≤ √n，循环总在那儿停 —— 上界写多大在这道题上是免费的\n");
    printf("\n③ int 够不够：题面里可能出现的最大「较小质数」= %lld（配 q = %lld）\n", maxP, maxQ);
    printf("   ⇒ i*i 最大 %lld，而 int 上限 %lld ⇒ **恰好够，余量 %.1f%%**\n",
           maxSq, INT_TOP, (double)(INT_TOP - maxSq) * 100.0 / (double)maxSq);
    printf("\n④ 次数：正解最坏 %lld 次；不 break 扫到底 %lld 次 ⇒ 差 %.0f 倍\n",
           maxP - 1, NMAX - 2, (double)(NMAX - 2) / (double)(maxP - 1));
    printf("   秒表：正解 %.3f 微秒（跑一万次取平均）；不 break 在 n = 2×10⁸ 上 %.0f 毫秒 ⇒ 顶格外推 %.1f 秒\n",
           usFast, msNoBreak, projNoBreakSec);
    printf("\n⑤ 「那就筛」：顶格要 %.0f MB，而题面给 128 MB ⇒ 差 %.1f 倍\n", sieveMB, sieveMB / limitMB);
    return 0;
}