自然数 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 = 9 千万個を割ることになり、Craykon は実行ステップ上限（約 5 千万）を超え、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); }}