PrefixComposite
TCO19 Round 3B · 2019-04-15 · by Errichto
Problem Statement
A number is composite if it is a positive integer with at least three divisors. The smallest few composite numbers are 4, 6, 8, 9, 10, 12, ...
A number is called prefix-composite if all its non-empty prefixes are composite. For example, the number 87343 is prefix-composite becase each of the numbers 8, 87, 873, 8734, and 87343 is composite.
Given two integers A and B, find the smallest and the greatest prefix-composite number in the closed interval [A, B].
Return a
Constraints
- A and B will be between 1 and 10^11, inclusive.
- A will be smaller than or equal to B.
1
3
Returns: { }
The number 1 is neither composite nor prime, and the numbers 2 and 3 are prime.
1
4
Returns: {4, 4 }
If there is exactly one prefix-composite number in the given interval, the return value should contain it twice - it is both the smallest and the greatest one in that range.
123
838
Returns: {400, 828 }
409
87343
Returns: {420, 87343 }
979797
979898
Returns: { }
37337999
37337999
Returns: { }
Fun fact: the number 37,337,999 is prefix-prime - each of its prefixes is prime.
Submissions are judged against all 262 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class PrefixComposite with a public method vector<long long> minMax(long long A, long long B) · 262 test cases · 2 s / 256 MB per case