PrefixComposite | Topcoder Archive

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 long[] with those two elements in the order {smallest, greatest}. If there are no prefix-composite numbers in the given interval, return an empty long[] instead.

Definition

Class:: PrefixComposite
Method:: minMax
Parameters:: long, long
Returns:: long[]
Method signature:: long[] minMax(long A, long B)
(be sure your method is public)

Constraints

A and B will be between 1 and 10^11, inclusive.
A will be smaller than or equal to B.

Examples

```
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: { }
```
```
600
```
```
703
```
```
Returns: {600, 699 }
```
```
1
```
```
100000000000
```
```
Returns: {4, 99999999999 }
```
```
37337999
```
```
37337999
```
```
Returns: { }
```
Fun fact: the number 37,337,999 is prefix-prime - each of its prefixes is prime.
```
22
```
```
39
```
```
Returns: { }
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.