1보다 큰 정수는 소수들의 곱으로 나타낼 수 있다. 예를 들어 48 = 2 × 2 × 2 × 2 × 3이고 49 = 7 × 7이다.
정수 x를 소수들의 곱으로 나타냈을 때 쓰인 소수가 모두 B 이하이면, x를 'B로 쪼개지는 수'라고 하자.
1은 소수를 하나도 쓰지 않으므로 B가 얼마이든 B로 쪼개지는 수다.
예를 들어 48은 3으로 쪼개지는 수이고, 49는 7로 쪼개지는 수이지만 5로 쪼개지는 수는 아니다.
질문이 q개 주어지고, 질문 하나는 세 정수 L, R, B다.
질문마다 L 이상 R 이하의 정수 가운데 B로 쪼개지는 수를 모두 찾는다.
그런 수가 있으면 그 개수, 가장 작은 것, 가장 큰 것을 빈칸 하나로 띄워 한 줄에 출력하라.
그런 수가 하나도 없으면 0만 출력하라.
입력
첫 줄에 q가 주어지고, 다음 q줄에 줄마다 L, R, B가 빈칸 하나로 나뉘어 주어진다. 1 ≤ q ≤ 100, 1 ≤ L ≤ R ≤ 81,000,000, R − L ≤ 8,999, 1 ≤ B ≤ 81,000,000. 모두 정수다
출력
질문마다 한 줄씩, B로 쪼개지는 수의 개수와 가장 작은 것과 가장 큰 것(쉼표 없이 숫자만), 또는 0
예시 1 · stdin
4
1 10 3
48 50 7
18000 18004 9001
14 14 5
stdout
7 1 9
3 48 50
5 18000 18004
0
main.py
오류 목록00F8 ↓ · ⇧F8 ↑
입력(stdin)
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
다른 언어로는?언어별 풀이 보기 · 8개 언어 풀이
수가 8,100만까지라 전체에 체를 칠 수는 없지만, 창 하나는 수가 9,000개뿐이에요. 그래서 9,000 이하의 소수만 에라토스테네스의 체로 구해 두고, 창 안에서 소수 p의 배수 자리만 건너뛰며 찾아가 p로 나눠요(구간 체). 수 하나하나를 소수로 나눠 보면 창 하나에 많게는 천만 번쯤 나누지만, 이렇게 하면 몇만 번이면 끝나요. 솔직히 말하면 C·C++처럼 빠른 언어에서는 수마다 p × p가 남은 수보다 커질 때 멈추는 나눠 보기로도 시간 안에 끝나요. Python과 크레이콘에서는 그렇게 하면 시간 한도를 넘어서 구간 체가 꼭 필요해요. 왜 9,000까지일까요? 9,000 × 9,000 = 81,000,000이라 9,000보다 큰 소수는 한 수에 많아야 한 번 들어 있어요. 그래서 B 이하의 작은 소수로 나눌 만큼 나누고 '남은 수'가 B 이하인지만 보면 돼요. 남은 수는 1이거나, 9,000보다 큰 소수 하나이거나, B보다 큰 소수들의 곱이에요. 함정 하나: 소수마다 한 번만 나누면 8 = 2 × 2 × 2에서 4가 남아, 첫 질문이 6 1 9가 돼요. 함정 둘: 남은 수가 1일 때만 세면 18002 = 2 × 9001을 놓쳐 셋째 질문이 4개가 돼요. 함정 셋: 'B 이하'예요. '미만'으로 쓰면 첫 질문에서 3을 못 써서 4 1 8이 돼요. 함정 넷: 1도 세요. 빼면 6 2 9가 돼요. 함정 다섯: 창에서 p의 첫 배수는 L 이상이어야 해요. L / p * p + p로 쓰면 L이 p의 배수일 때 L을 건너뛰어 둘째 질문이 2 49 50이 돼요. 함정 여섯: 정수 나눗셈이에요. (L + p - 1) / p * p는 Java·C#·C·C++에서는 /가 몫이라 맞지만, JS·TS·크레이콘의 /는 소수까지 나눠서 그냥 L + p − 1이 되고 둘째 질문이 0이 돼요. JS·TS는 Math.ceil(L / p) * p나 Math.floor, 크레이콘은 수학.몫(L + p - 1, p) * p, Python은 //를 써요. 함정 일곱: 작은 소수를 1,000까지만 구하면 1009 × 1013 = 1,022,117 같은 수가 통째로 남아요. B = 2,000일 때 쪼개지는 수인데 아니라고 답해요.
Pythonmain.py · 43 줄
import sysROOT = 9000 # 9000 × 9000 = 81,000,000: 이보다 큰 소수는 한 수에 많아야 한 번 들어 있다def main(): data = sys.stdin.read().split() q = int(data[0]) # 에라토스테네스의 체로 9,000 이하의 소수를 모은다 is_prime = [True] * (ROOT + 1) is_prime[0] = is_prime[1] = False primes = [] for i in range(2, ROOT + 1): if is_prime[i]: primes.append(i) for j in range(i * i, ROOT + 1, i): is_prime[j] = False out = [] for i in range(q): lo, hi, b = int(data[1 + 3 * i]), int(data[2 + 3 * i]), int(data[3 + 3 * i]) # rest[x - lo]: x에서 b 이하의 작은 소수를 모두 나누어 없애고 남은 수 rest = list(range(lo, hi + 1)) for p in primes: if p > b: break first = (lo + p - 1) // p * p # lo 이상인 첫 p의 배수 for x in range(first, hi + 1, p): r = rest[x - lo] while r % p == 0: r //= p rest[x - lo] = r # 남은 수가 1이 아니면 9,000보다 큰 소수 하나이거나, b보다 큰 소수들의 곱이다 good = [lo + k for k, r in enumerate(rest) if r <= b] if good: out.append(f"{len(good)} {good[0]} {good[-1]}") else: out.append("0") print("\n".join(out))main()
JavaScriptmain.js · 42 줄
const data = require("fs").readFileSync(0, "utf8").split(/\s+/).filter(Boolean).map(Number);const q = data[0];const ROOT = 9000; // 9000 × 9000 = 81,000,000: 이보다 큰 소수는 한 수에 많아야 한 번 들어 있다// 에라토스테네스의 체로 9,000 이하의 소수를 모은다const isPrime = new Array(ROOT + 1).fill(true);isPrime[0] = isPrime[1] = false;const primes = [];for (let i = 2; i <= ROOT; i++) { if (isPrime[i]) { primes.push(i); for (let j = i * i; j <= ROOT; j += i) isPrime[j] = false; }}const out = [];for (let i = 0; i < q; i++) { const lo = data[1 + 3 * i], hi = data[2 + 3 * i], b = data[3 + 3 * i]; // rest[x - lo]: x에서 b 이하의 작은 소수를 모두 나누어 없애고 남은 수 const rest = []; for (let x = lo; x <= hi; x++) rest.push(x); for (const p of primes) { if (p > b) break; const first = Math.ceil(lo / p) * p; // lo 이상인 첫 p의 배수. `/`는 소수가 나오므로 올림한다 for (let x = first; x <= hi; x += p) { let r = rest[x - lo]; while (r % p === 0) r /= p; rest[x - lo] = r; } } // 남은 수가 1이 아니면 9,000보다 큰 소수 하나이거나, b보다 큰 소수들의 곱이다 let count = 0, smallest = 0, largest = 0; for (let x = lo; x <= hi; x++) { if (rest[x - lo] <= b) { if (count === 0) smallest = x; largest = x; count++; } } out.push(count > 0 ? `${count} ${smallest} ${largest}` : "0");}console.log(out.join("\n"));
TypeScriptmain.ts · 42 줄
const data = require("fs").readFileSync(0, "utf8").split(/\s+/).filter(Boolean).map(Number);const q = data[0];const ROOT = 9000; // 9000 × 9000 = 81,000,000: 이보다 큰 소수는 한 수에 많아야 한 번 들어 있다// 에라토스테네스의 체로 9,000 이하의 소수를 모은다const isPrime: boolean[] = new Array(ROOT + 1).fill(true);isPrime[0] = isPrime[1] = false;const primes: number[] = [];for (let i = 2; i <= ROOT; i++) { if (isPrime[i]) { primes.push(i); for (let j = i * i; j <= ROOT; j += i) isPrime[j] = false; }}const out: string[] = [];for (let i = 0; i < q; i++) { const lo = data[1 + 3 * i], hi = data[2 + 3 * i], b = data[3 + 3 * i]; // rest[x - lo]: x에서 b 이하의 작은 소수를 모두 나누어 없애고 남은 수 const rest: number[] = []; for (let x = lo; x <= hi; x++) rest.push(x); for (const p of primes) { if (p > b) break; const first = Math.ceil(lo / p) * p; // lo 이상인 첫 p의 배수. `/`는 소수가 나오므로 올림한다 for (let x = first; x <= hi; x += p) { let r = rest[x - lo]; while (r % p === 0) r /= p; rest[x - lo] = r; } } // 남은 수가 1이 아니면 9,000보다 큰 소수 하나이거나, b보다 큰 소수들의 곱이다 let count = 0, smallest = 0, largest = 0; for (let x = lo; x <= hi; x++) { if (rest[x - lo] <= b) { if (count === 0) smallest = x; largest = x; count++; } } out.push(count > 0 ? `${count} ${smallest} ${largest}` : "0");}console.log(out.join("\n"));
JavaMain.java · 49 줄
import java.util.*;public class Main { static final int ROOT = 9000; // 9000 × 9000 = 81,000,000: 이보다 큰 소수는 한 수에 많아야 한 번 들어 있다 public static void main(String[] args) { Scanner in = new Scanner(System.in); int q = in.nextInt(); // 에라토스테네스의 체로 9,000 이하의 소수를 모은다 boolean[] composite = new boolean[ROOT + 1]; List<Integer> primes = new ArrayList<>(); for (int i = 2; i <= ROOT; i++) { if (!composite[i]) { primes.add(i); for (int j = i * i; j <= ROOT; j += i) composite[j] = true; } } StringBuilder out = new StringBuilder(); for (int i = 0; i < q; i++) { int lo = in.nextInt(), hi = in.nextInt(), b = in.nextInt(); // rest[x - lo]: x에서 b 이하의 작은 소수를 모두 나누어 없애고 남은 수 int[] rest = new int[hi - lo + 1]; for (int x = lo; x <= hi; x++) rest[x - lo] = x; for (int p : primes) { if (p > b) break; int first = (lo + p - 1) / p * p; // lo 이상인 첫 p의 배수(정수 나눗셈) for (int x = first; x <= hi; x += p) { int r = rest[x - lo]; while (r % p == 0) r /= p; rest[x - lo] = r; } } // 남은 수가 1이 아니면 9,000보다 큰 소수 하나이거나, b보다 큰 소수들의 곱이다 int count = 0, smallest = 0, largest = 0; for (int x = lo; x <= hi; x++) { if (rest[x - lo] <= b) { if (count == 0) smallest = x; largest = x; count++; } } if (count > 0) out.append(count).append(' ').append(smallest).append(' ').append(largest).append('\n'); else out.append("0\n"); } System.out.print(out); }}
C#Main.cs · 60 줄
using System;using System.Collections.Generic;using System.Text;class Program{ const int Root = 9000; // 9000 × 9000 = 81,000,000: 이보다 큰 소수는 한 수에 많아야 한 번 들어 있다 static void Main() { string[] data = Console.In.ReadToEnd().Split((char[])null, StringSplitOptions.RemoveEmptyEntries); int q = int.Parse(data[0]); // 에라토스테네스의 체로 9,000 이하의 소수를 모은다 var composite = new bool[Root + 1]; var primes = new List<int>(); for (int i = 2; i <= Root; i++) { if (!composite[i]) { primes.Add(i); for (int j = i * i; j <= Root; j += i) composite[j] = true; } } var output = new StringBuilder(); for (int i = 0; i < q; i++) { int lo = int.Parse(data[1 + 3 * i]), hi = int.Parse(data[2 + 3 * i]), b = int.Parse(data[3 + 3 * i]); // rest[x - lo]: x에서 b 이하의 작은 소수를 모두 나누어 없애고 남은 수 var rest = new int[hi - lo + 1]; for (int x = lo; x <= hi; x++) rest[x - lo] = x; foreach (int p in primes) { if (p > b) break; int first = (lo + p - 1) / p * p; // lo 이상인 첫 p의 배수(정수 나눗셈) for (int x = first; x <= hi; x += p) { int r = rest[x - lo]; while (r % p == 0) r /= p; rest[x - lo] = r; } } // 남은 수가 1이 아니면 9,000보다 큰 소수 하나이거나, b보다 큰 소수들의 곱이다 int count = 0, smallest = 0, largest = 0; for (int x = lo; x <= hi; x++) { if (rest[x - lo] <= b) { if (count == 0) smallest = x; largest = x; count++; } } if (count > 0) output.Append(count).Append(' ').Append(smallest).Append(' ').Append(largest).Append('\n'); else output.Append("0\n"); } Console.Write(output); }}
C++main.cpp · 52 줄
#include <iostream>#include <numeric>#include <vector>using namespace std;const int ROOT = 9000; // 9000 × 9000 = 81,000,000: 이보다 큰 소수는 한 수에 많아야 한 번 들어 있다int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int q; cin >> q; // 에라토스테네스의 체로 9,000 이하의 소수를 모은다 vector<bool> composite(ROOT + 1, false); vector<int> primes; for (int i = 2; i <= ROOT; i++) { if (!composite[i]) { primes.push_back(i); for (int j = i * i; j <= ROOT; j += i) composite[j] = true; } } while (q-- > 0) { int lo, hi, b; cin >> lo >> hi >> b; // rest[x - lo]: x에서 b 이하의 작은 소수를 모두 나누어 없애고 남은 수 vector<int> rest(hi - lo + 1); iota(rest.begin(), rest.end(), lo); for (int p : primes) { if (p > b) break; int first = (lo + p - 1) / p * p; // lo 이상인 첫 p의 배수(정수 나눗셈) for (int x = first; x <= hi; x += p) { int r = rest[x - lo]; while (r % p == 0) r /= p; rest[x - lo] = r; } } // 남은 수가 1이 아니면 9,000보다 큰 소수 하나이거나, b보다 큰 소수들의 곱이다 int count = 0, smallest = 0, largest = 0; for (int x = lo; x <= hi; x++) { if (rest[x - lo] <= b) { if (count == 0) smallest = x; largest = x; count++; } } if (count > 0) cout << count << ' ' << smallest << ' ' << largest << '\n'; else cout << "0\n"; } return 0;}
Cmain.c · 49 줄
#include <stdio.h>#define ROOT 9000 /* 9000 × 9000 = 81,000,000: 이보다 큰 소수는 한 수에 많아야 한 번 들어 있다 */#define SPAN 9000 /* 창 하나에 들어가는 수의 최대 개수 */static char composite[ROOT + 1];static int primes[ROOT], prime_count = 0;static int rest[SPAN];int main(void) { int q; if (scanf("%d", &q) != 1) return 1; /* 에라토스테네스의 체로 9,000 이하의 소수를 모은다 */ for (int i = 2; i <= ROOT; i++) { if (!composite[i]) { primes[prime_count++] = i; for (int j = i * i; j <= ROOT; j += i) composite[j] = 1; } } while (q-- > 0) { int lo, hi, b; scanf("%d %d %d", &lo, &hi, &b); /* rest[x - lo]: x에서 b 이하의 작은 소수를 모두 나누어 없애고 남은 수 */ for (int x = lo; x <= hi; x++) rest[x - lo] = x; for (int k = 0; k < prime_count && primes[k] <= b; k++) { int p = primes[k]; int first = (lo + p - 1) / p * p; /* lo 이상인 첫 p의 배수(정수 나눗셈) */ for (int x = first; x <= hi; x += p) { int r = rest[x - lo]; while (r % p == 0) r /= p; rest[x - lo] = r; } } /* 남은 수가 1이 아니면 9,000보다 큰 소수 하나이거나, b보다 큰 소수들의 곱이다 */ int count = 0, smallest = 0, largest = 0; for (int x = lo; x <= hi; x++) { if (rest[x - lo] <= b) { if (count == 0) smallest = x; largest = x; count++; } } if (count > 0) printf("%d %d %d\n", count, smallest, largest); else printf("0\n"); } return 0;}
Craykonmain.cray · 72 줄
q = 콘솔.줄읽기().수로변환();뿌리 = 9000; // 9000 × 9000 = 81,000,000: 이보다 큰 소수는 한 수에 많아야 한 번 들어 있다// 에라토스테네스의 체로 9,000 이하의 소수를 모은다소수인가 = 새목록(뿌리 + 1, 참);소수들 = [];반복 (i = 2; i <= 뿌리; i++){ 만약 (소수인가[i]) { 소수들.넣기(i); 반복 (j = i * i; j <= 뿌리; j += i) { 소수인가[j] = 거짓; } }}반복 (i = 0; i < q; i++){ 줄 = 콘솔.수들읽기(); lo = 줄[0]; hi = 줄[1]; b = 줄[2]; // 남은수[x - lo]: x에서 b 이하의 작은 소수를 모두 나누어 없애고 남은 수 남은수 = []; 반복 (x = lo; x <= hi; x++) { 남은수.넣기(x); } 각각 (p 에서 소수들) { 만약 (p > b) { 그만; } 첫배수 = 수학.몫(lo + p - 1, p) * p; // lo 이상인 첫 p의 배수. `/`는 소수가 나오므로 몫을 쓴다 반복 (x = 첫배수; x <= hi; x += p) { r = 남은수[x - lo]; 동안 (r % p == 0) { r = 수학.몫(r, p); } 남은수[x - lo] = r; } } // 남은 수가 1이 아니면 9,000보다 큰 소수 하나이거나, b보다 큰 소수들의 곱이다 개수 = 0; 가장작은 = 0; 가장큰 = 0; 반복 (x = lo; x <= hi; x++) { 만약 (남은수[x - lo] <= b) { 만약 (개수 == 0) { 가장작은 = x; } 가장큰 = x; 개수 += 1; } } 만약 (개수 > 0) { 콘솔.쓰기([개수, 가장작은, 가장큰]); } 아니면 { 콘솔.쓰기(0); }}