An integer greater than 1 can be written as a product of primes. For example 48 = 2 × 2 × 2 × 2 × 3 and 49 = 7 × 7.
When an integer x is written as a product of primes and every prime used is at most B, call x a 'number that splits by B'.
1 uses no primes at all, so it is a number that splits by B whatever B is.
For example 48 splits by 3, and 49 splits by 7 but does not split by 5.
There are q questions, and each question is three integers L, R and B.
For each question, find every integer from L to R inclusive that splits by B.
If there are such numbers, print how many there are, the smallest one and the largest one on one line, separated by single spaces.
If there are none, print only 0.
Input
The first line has q, and each of the next q lines has L, R and B separated by single spaces. 1 ≤ q ≤ 100, 1 ≤ L ≤ R ≤ 81,000,000, R − L ≤ 8,999, 1 ≤ B ≤ 81,000,000. All are integers
Output
One line per question: the count of numbers that split by B, the smallest and the largest (digits only, no commas), or 0
Example 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
Error List00F8 ↓ · ⇧F8 ↑
Input (stdin)
When you run, these lines are fed to input()/stdin in order (the program doesn't stop to ask).
$ Ready
Open this on a computer to write and run code. On mobile you can read the problem and the solutions.
In other languagesShow solutions by language · 8 languages
The numbers go up to 81 million, so you cannot sieve all of them, but one window holds only 9,000 numbers. So find just the primes up to 9,000 with the sieve of Eratosthenes, and inside the window jump straight to the multiples of each prime p and divide by p (a segmented sieve). Trying primes on each number one by one can take around ten million divisions per window, while this takes a few tens of thousands. To be honest, in fast languages such as C and C++, trial division that stops once p × p is greater than what is left of the number also finishes in time. In Python and Craykon that goes over the time limit, so the segmented sieve is really needed there. Why 9,000? 9,000 × 9,000 = 81,000,000, so a prime greater than 9,000 appears at most once in a number. So divide by the small primes up to B as many times as possible and only check whether 'what is left' is at most B. What is left is 1, or a single prime greater than 9,000, or a product of primes greater than B. Trap one: divide only once per prime and 8 = 2 × 2 × 2 leaves 4, so the first question gives 6 1 9. Trap two: count only when 1 is left and you miss 18002 = 2 × 9001, so the third question gives 4 numbers. Trap three: it is 'at most B'. Write 'less than' and 3 cannot be used in the first question, giving 4 1 8. Trap four: 1 counts too. Leave it out and you get 6 2 9. Trap five: the first multiple of p in the window must be at least L. Write L / p * p + p and L is skipped when L is a multiple of p, so the second question gives 2 49 50. Trap six: integer division. (L + p - 1) / p * p is right in Java, C#, C and C++ because / gives the quotient, but in JS, TS and Craykon / divides into decimals, so it is simply L + p − 1 and the second question gives 0. Use Math.ceil(L / p) * p or Math.floor in JS and TS, Mathf.Quot(L + p - 1, p) * p in Craykon, and // in Python. Trap seven: find small primes only up to 1,000 and a number like 1009 × 1013 = 1,022,117 is left whole. With B = 2,000 it does split, but the answer says it does not.
Pythonmain.py · 43 lines
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 lines
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 lines
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 lines
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 lines
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 lines
#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 lines
#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 lines
q = Console.ReadLine().ToNumber();뿌리 = 9000; // 9000 × 9000 = 81,000,000: 이보다 큰 소수는 한 수에 많아야 한 번 들어 있다// 에라토스테네스의 체로 9,000 이하의 소수를 모은다소수인가 = NewList(뿌리 + 1, true);소수들 = [];for (i = 2; i <= 뿌리; i++){ if (소수인가[i]) { 소수들.Add(i); for (j = i * i; j <= 뿌리; j += i) { 소수인가[j] = false; } }}for (i = 0; i < q; i++){ 줄 = Console.ReadNumbers(); lo = 줄[0]; hi = 줄[1]; b = 줄[2]; // 남은수[x - lo]: x에서 b 이하의 작은 소수를 모두 나누어 없애고 남은 수 남은수 = []; for (x = lo; x <= hi; x++) { 남은수.Add(x); } foreach (p in 소수들) { if (p > b) { break; } 첫배수 = Mathf.Quot(lo + p - 1, p) * p; // lo 이상인 첫 p의 배수. `/`는 소수가 나오므로 몫을 쓴다 for (x = 첫배수; x <= hi; x += p) { r = 남은수[x - lo]; while (r % p == 0) { r = Mathf.Quot(r, p); } 남은수[x - lo] = r; } } // 남은 수가 1이 아니면 9,000보다 큰 소수 하나이거나, b보다 큰 소수들의 곱이다 개수 = 0; 가장작은 = 0; 가장큰 = 0; for (x = lo; x <= hi; x++) { if (남은수[x - lo] <= b) { if (개수 == 0) { 가장작은 = x; } 가장큰 = x; 개수 += 1; } } if (개수 > 0) { Console.WriteLine([개수, 가장작은, 가장큰]); } else { Console.WriteLine(0); }}