把自然数 x 写成素数的乘积时，相乘的素数个数记为 Ω(x)。
同一个素数乘了几次就算几个（12 = 2 × 2 × 3，所以 Ω(12) = 3）。
素数 p 的 Ω(p) = 1，1 没有相乘的素数，所以 Ω(1) = 0。
给出 q 个询问。
对每个询问，输出一行：在 l 到 r（含两端）的自然数 x 中，Ω(x) = k 的有多少个。
第一行给出 q，接下来 q 行每行给出用空格隔开的 l、r、k。
3 1 12 2 2 2 1 12 12 3
4 1 1
2 1 1 0 1 9000 14
1 0
运行时这些行会依次作为 input()/标准输入传入(运行中不会等待输入)。
$ 就绪
请在电脑上打开以编写和运行代码。在手机上可以查看题目和题解。
每个询问都把 l..r 的数逐个分解质因数，要处理 10,000 × 9,000 = 九千万个数，Craykon 会超过执行步数上限（约五千万），Python 也要几十秒。
所以先建两张表。
① 最小质因数筛：像埃拉托斯特尼筛法那样，但不是划掉素数 i 的倍数，而是记下 spf[j] = i（不覆盖先写下的值），这样就能从小到大逐个填出 Ω(x) = Ω(x / spf[x]) + 1。
② 前缀和：设 count[k][x] =「1..x 中 Ω 等于 k 的数的个数」，答案就是 count[k][r] − count[k][l − 1]。
减去 l − 1 处的值，l 本身才会被算进去。
因为 2¹³ = 8192 ≤ 9000 < 2¹⁴，Ω 不会超过 13，表有 14 行就够了；k 大于 13 的询问不要读表，直接答 0（否则 Python、JavaScript、Java、C# 会报错，C、C++ 会读到数组外）。
如果同一个素数只算一次（不同质因数的个数），12 就变成 2，答案错误。
建二维表的方法各语言不同：Python 必须像 [[0] * (N + 1) for _ in range(14)] 这样每行新建——[[0] * (N + 1)] * 14 让 14 行都指向同一行，改一行全部都变。
JavaScript/TypeScript 的 Array(14).fill([]) 也是同样的陷阱，要用 Array.from({ length: 14 }, () => new Array(N + 1).fill(0))。
Java new int[14][N + 1]、C# new int[14, N + 1]（矩形数组，用 count[k, x] 读取）、C++ std::vector<std::vector<int>>(14, std::vector<int>(N + 1)) 都会分别建好每一行，C 的 static int count[14][N + 1] 初始为 0。
Craykon 的 新列表(14, 新列表(N + 1, 0)) 会把列表复制到每一格，所以各行不会绑在一起。
Craykon 的列表最多 10,000 项，所以 r 只到 9,000。
import sys N = 9000MAXK = 13 # 2¹³ = 8192 ≤ 9000 < 2¹⁴ 이라 Ω는 13을 넘지 않는다 # 가장 작은 소인수 체: spf[x]는 x를 나누는 가장 작은 소수spf = list(range(N + 1))for i in range(2, int(N ** 0.5) + 1): if spf[i] == i: # i는 소수 for j in range(i * i, N + 1, i): if spf[j] == j: spf[j] = i # Ω(x) = Ω(x / spf[x]) + 1, Ω(1) = 0omega = [0] * (N + 1)for x in range(2, N + 1): omega[x] = omega[x // spf[x]] + 1 # count[k][x] = 1..x 가운데 Ω가 k인 수의 개수(누적 합). 줄마다 새 목록을 만든다.count = [[0] * (N + 1) for _ in range(MAXK + 1)]for k in range(MAXK + 1): row = count[k] for x in range(1, N + 1): row[x] = row[x - 1] + (omega[x] == k) data = sys.stdin.read().split()q = int(data[0])out = []for t in range(q): l, r, k = (int(v) for v in data[1 + 3 * t: 4 + 3 * t]) out.append(count[k][r] - count[k][l - 1] if k <= MAXK else 0)print("\n".join(map(str, out)))const N = 9000;const MAXK = 13; // 2¹³ = 8192 ≤ 9000 < 2¹⁴ 이라 Ω는 13을 넘지 않는다 // 가장 작은 소인수 체: spf[x]는 x를 나누는 가장 작은 소수const spf = Array.from({ length: N + 1 }, (_, x) => x);for (let i = 2; i * i <= N; i++) { if (spf[i] !== i) continue; for (let j = i * i; j <= N; j += i) if (spf[j] === j) spf[j] = i;} // Ω(x) = Ω(x / spf[x]) + 1, Ω(1) = 0const omega = new Array(N + 1).fill(0);for (let x = 2; x <= N; x++) omega[x] = omega[x / spf[x]] + 1; // count[k][x] = 1..x 가운데 Ω가 k인 수의 개수. fill([])처럼 한 배열을 나눠 쓰지 않게 줄마다 만든다.const count = Array.from({ length: MAXK + 1 }, () => new Array(N + 1).fill(0));for (let k = 0; k <= MAXK; k++) { for (let x = 1; x <= N; x++) count[k][x] = count[k][x - 1] + (omega[x] === k ? 1 : 0);} const [q, ...rest] = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const out = [];for (let t = 0; t < q; t++) { const [l, r, k] = rest.slice(3 * t, 3 * t + 3); out.push(k <= MAXK ? count[k][r] - count[k][l - 1] : 0);}console.log(out.join("\n"));import { readFileSync } from "node:fs"; const N = 9000;const MAXK = 13; // 2¹³ = 8192 ≤ 9000 < 2¹⁴ 이라 Ω는 13을 넘지 않는다 // 가장 작은 소인수 체: spf[x]는 x를 나누는 가장 작은 소수const spf: number[] = Array.from({ length: N + 1 }, (_, x) => x);for (let i = 2; i * i <= N; i++) { if (spf[i] !== i) continue; for (let j = i * i; j <= N; j += i) if (spf[j] === j) spf[j] = i;} // Ω(x) = Ω(x / spf[x]) + 1, Ω(1) = 0const omega: number[] = new Array<number>(N + 1).fill(0);for (let x = 2; x <= N; x++) omega[x] = omega[x / spf[x]] + 1; // count[k][x] = 1..x 가운데 Ω가 k인 수의 개수. fill([])처럼 한 배열을 나눠 쓰지 않게 줄마다 만든다.const count: number[][] = Array.from({ length: MAXK + 1 }, () => new Array<number>(N + 1).fill(0));for (let k = 0; k <= MAXK; k++) { for (let x = 1; x <= N; x++) count[k][x] = count[k][x - 1] + (omega[x] === k ? 1 : 0);} const [q, ...rest]: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const out: number[] = [];for (let t = 0; t < q; t++) { const [l, r, k] = rest.slice(3 * t, 3 * t + 3); out.push(k <= MAXK ? count[k][r] - count[k][l - 1] : 0);}console.log(out.join("\n"));import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer; public class Main { static final int N = 9000; static final int MAXK = 13; // 2¹³ = 8192 ≤ 9000 < 2¹⁴ 이라 Ω는 13을 넘지 않는다 public static void main(String[] args) throws IOException { // 가장 작은 소인수 체: spf[x]는 x를 나누는 가장 작은 소수 int[] spf = new int[N + 1]; for (int x = 0; x <= N; x++) spf[x] = x; for (int i = 2; i * i <= N; i++) { if (spf[i] != i) continue; for (int j = i * i; j <= N; j += i) if (spf[j] == j) spf[j] = i; } // Ω(x) = Ω(x / spf[x]) + 1, Ω(1) = 0 int[] omega = new int[N + 1]; for (int x = 2; x <= N; x++) omega[x] = omega[x / spf[x]] + 1; // count[k][x] = 1..x 가운데 Ω가 k인 수의 개수. new int[a][b]는 줄마다 따로 만들어진다. int[][] count = new int[MAXK + 1][N + 1]; for (int k = 0; k <= MAXK; k++) for (int x = 1; x <= N; x++) count[k][x] = count[k][x - 1] + (omega[x] == k ? 1 : 0); BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); int q = Integer.parseInt(in.readLine().trim()); StringBuilder out = new StringBuilder(); for (int t = 0; t < q; t++) { StringTokenizer st = new StringTokenizer(in.readLine()); int l = Integer.parseInt(st.nextToken()); int r = Integer.parseInt(st.nextToken()); int k = Integer.parseInt(st.nextToken()); out.append(k <= MAXK ? count[k][r] - count[k][l - 1] : 0).append('\n'); } System.out.print(out); }}using System;using System.Text; class Program{ const int N = 9000; const int MAXK = 13; // 2¹³ = 8192 ≤ 9000 < 2¹⁴ 이라 Ω는 13을 넘지 않는다 static void Main() { // 가장 작은 소인수 체: spf[x]는 x를 나누는 가장 작은 소수 int[] spf = new int[N + 1]; for (int x = 0; x <= N; x++) spf[x] = x; for (int i = 2; i * i <= N; i++) { if (spf[i] != i) continue; for (int j = i * i; j <= N; j += i) if (spf[j] == j) spf[j] = i; } // Ω(x) = Ω(x / spf[x]) + 1, Ω(1) = 0 int[] omega = new int[N + 1]; for (int x = 2; x <= N; x++) omega[x] = omega[x / spf[x]] + 1; // count[k, x] = 1..x 가운데 Ω가 k인 수의 개수(2차원 배열) int[,] count = new int[MAXK + 1, N + 1]; for (int k = 0; k <= MAXK; k++) for (int x = 1; x <= N; x++) count[k, x] = count[k, x - 1] + (omega[x] == k ? 1 : 0); int q = int.Parse(Console.ReadLine().Trim()); var out_ = new StringBuilder(); for (int t = 0; t < q; t++) { string[] p = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); int l = int.Parse(p[0]), r = int.Parse(p[1]), k = int.Parse(p[2]); out_.Append(k <= MAXK ? count[k, r] - count[k, l - 1] : 0).Append('\n'); } Console.Write(out_); }}#include <iostream>#include <vector> int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); const int N = 9000; const int MAXK = 13; // 2¹³ = 8192 ≤ 9000 < 2¹⁴ 이라 Ω는 13을 넘지 않는다 // 가장 작은 소인수 체: spf[x]는 x를 나누는 가장 작은 소수 std::vector<int> spf(N + 1); for (int x = 0; x <= N; x++) spf[x] = x; for (int i = 2; i * i <= N; i++) { if (spf[i] != i) continue; for (int j = i * i; j <= N; j += i) if (spf[j] == j) spf[j] = i; } // Ω(x) = Ω(x / spf[x]) + 1, Ω(1) = 0 std::vector<int> omega(N + 1, 0); for (int x = 2; x <= N; x++) omega[x] = omega[x / spf[x]] + 1; // count[k][x] = 1..x 가운데 Ω가 k인 수의 개수. vector(줄 수, 한 줄)는 줄마다 복사해 만든다. std::vector<std::vector<int>> count(MAXK + 1, std::vector<int>(N + 1, 0)); for (int k = 0; k <= MAXK; k++) for (int x = 1; x <= N; x++) count[k][x] = count[k][x - 1] + (omega[x] == k ? 1 : 0); int q, l, r, k; std::cin >> q; while (q--) { std::cin >> l >> r >> k; std::cout << (k <= MAXK ? count[k][r] - count[k][l - 1] : 0) << "\n"; }}#include <stdio.h> #define N 9000#define MAXK 13 /* 2¹³ = 8192 ≤ 9000 < 2¹⁴ 이라 Ω는 13을 넘지 않는다 */ static int spf[N + 1], omega[N + 1];static int count[MAXK + 1][N + 1]; /* static 배열은 0으로 시작한다 */ int main(void) { /* 가장 작은 소인수 체: spf[x]는 x를 나누는 가장 작은 소수 */ for (int x = 0; x <= N; x++) spf[x] = x; for (int i = 2; i * i <= N; i++) { if (spf[i] != i) continue; for (int j = i * i; j <= N; j += i) if (spf[j] == j) spf[j] = i; } /* Ω(x) = Ω(x / spf[x]) + 1, Ω(1) = 0 */ for (int x = 2; x <= N; x++) omega[x] = omega[x / spf[x]] + 1; /* count[k][x] = 1..x 가운데 Ω가 k인 수의 개수 */ for (int k = 0; k <= MAXK; k++) for (int x = 1; x <= N; x++) count[k][x] = count[k][x - 1] + (omega[x] == k); int q, l, r, k; scanf("%d", &q); while (q--) { scanf("%d %d %d", &l, &r, &k); printf("%d\n", k <= MAXK ? count[k][r] - count[k][l - 1] : 0); /* k > 13이면 배열 밖이라 먼저 막는다 */ } return 0;}N = 9000;// 2의 13제곱 = 8192 ≤ 9000 이라 곱한 소수는 13개를 넘지 않는다MAXK = 13; // 가장 작은 소인수 체: spf[x]는 x를 나누는 가장 작은 소수spf = 新列表(N + 1, 0);循环 (x = 0; x <= N; x++){ spf[x] = x;}循环 (i = 2; i * i <= N; i++){ 如果 (spf[i] == i) { 循环 (j = i * i; j <= N; j += i) { 如果 (spf[j] == j) { spf[j] = i; } } }} // omega[x] = omega[x / spf[x]] + 1, omega[1] = 0omega = 新列表(N + 1, 0);循环 (x = 2; x <= N; x++){ omega[x] = omega[x / spf[x]] + 1;} // count[k][x] = 1..x 가운데 omega가 k인 수의 개수. 새목록에 목록을 넣으면 칸마다 따로 복사된다.count = 新列表(MAXK + 1, 新列表(N + 1, 0));循环 (k = 0; k <= MAXK; k++){ row = count[k]; 循环 (x = 1; x <= N; x++) { row[x] = row[x - 1]; 如果 (omega[x] == k) { row[x] += 1; } }} q = 控制台.读行().转数字();循环 (t = 0; t < q; t++){ 질문 = 控制台.读数字(); l = 질문[0]; r = 질문[1]; k = 질문[2]; 如果 (k <= MAXK) { 控制台.输出(count[k][r] - count[k][l - 1]); } 否则 { 控制台.输出(0); }}