随机数与质数

如何由小范围随机数构造大范围随机数？

• 基础公式: (randX() - 1) * Y + randY() 能等概率生成 $[1, X \times Y]$ 的整数;
• 原理: 先由 randX() 决定高位区间, 再由 randY() 填充区间内的偏移;
• 步骤: 先用公式构造一个范围比目标大的随机数, 再用取模加拒绝采样缩小到目标范围;

如何用 rand7 实现 rand10？

• 构造: (rand7() - 1) * 7 + rand7() 得到等概率的 $[1, 49]$;
• 拒绝采样: 结果大于 40 时重新随机, 保证 40 是 10 的整数倍;
• 映射: (res % 10) + 1 得到 $[1, 10]$;

const rand10 = () => {
  const rand49 = () => (rand7() - 1) * 7 + rand7();
  let res = rand49();
  while (res > 40) res = rand49(); // 拒绝采样, 保持等概率
  return (res % 10) + 1;
};

• 复杂度: 期望时间 $O(1)$, 空间 $O(1)$;
• 关键: 被拒绝区间长度必须是目标范围长度的整数倍, 否则概率不均;

如何由大范围随机数构造小范围随机数？

• 思路: 找一个不超过目标范围的最大整数倍 $x$;
• 拒绝: randN() 大于 $x$ 时重新随机;
• 映射: (value % m) + 1 得到 randM();
• 一致性: 与"小变大"一样, 靠拒绝采样保证等概率;

埃氏筛如何统计质数个数？

• 定义: 从 2 开始, 把每个质数的倍数全部标记为合数;
• 起点: 内层循环从 $i \times i$ 开始, 因为更小的倍数已被更小的质数标记过;
• 上界: 外层只需枚举到 $\sqrt{n}$, 更大的质数其平方已超出范围;
• 前提: isPrime 数组初始全为 true, 下标 0 与 1 不参与统计;

const countPrimes = (n) => {
  const isPrime = new Array(n).fill(true);
  for (let i = 2; i * i < n; i++) {
    if (!isPrime[i]) continue;
    for (let j = i * i; j < n; j += i) isPrime[j] = false;
  }
  let res = 0;
  for (let i = 2; i < n; i++) if (isPrime[i]) res++;
  return res;
};

• 复杂度: 时间 $O(n \log \log n)$, 空间 $O(n)$;
• 对比: 逐个试除判定质数是 $O(n\sqrt{n})$, 埃氏筛在批量场景更快;