数は 8,100 万まであるので全体にふるいをかけることはできませんが、一つの窓には数が 9,000 個しかありません。 そこで 9,000 以下の素数だけをエラトステネスのふるいで求めておき、窓の中で素数 p の倍数の位置だけを飛び飛びに訪ねて p で割ります（区間ふるい）。 数を一つずつ素数で割ってみると一つの窓で多ければ一千万回ほど割りますが、こうすれば数万回で済みます。 正直に言うと、C・C++ のような速い言語では、p × p が残った数より大きくなったらやめる試し割りでも時間内に終わります。 Python と Craykon ではそれだと制限時間を超えるので、区間ふるいがどうしても必要です。 なぜ 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・Craykon の / は小数まで割るので、ただの L + p − 1 になり、二つ目の質問が 0 になります。 JS・TS は Math.ceil(L / p) * p か Math.floor、Craykon は 数学.商(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); }}