자연수 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()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
질문마다 l..r의 수를 하나씩 소인수분해하면 10,000 × 9,000 = 9천만 개를 나눠 봐야 해서 크레이콘은 실행 걸음 한도(약 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가 되어 틀려요.
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으로 시작해요.
크레이콘 새목록(14, 새목록(N + 1, 0))은 칸마다 목록을 복사해서 줄이 묶이지 않아요.
크레이콘 목록은 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); }}