AlmostPrimeNumbers | Topcoder Archive

Problem Statement

An integer N greater than 1 is called almost prime if and only if the following conditions hold:

N is not prime. In other words, it is divisible by some positive integer other than 1 and itself.
Each positive divisor of N (other than 1) is greater than 10.

Return the smallest almost prime number that is strictly greater than m.

Definition

Class:: AlmostPrimeNumbers
Method:: getNext
Parameters:: int
Returns:: int
Method signature:: int getNext(int m)
(be sure your method is public)

Constraints

m will be between 1 and 10^6, inclusive.

Examples

```
200
```
```
Returns: 209
```
201 is divisible by 3, which is less than 10, so 201 is not almost prime. 202, 204, 206, and 208 are all divisible by 2. 203 is divisible by 7, 205 by 5, and 207 by 3. So, the smallest almost prime number greater than 200 is 209 = 11*19.
```
666
```
```
Returns: 667
```
667 = 23*29, so it's almost prime.
```
1000
```
```
Returns: 1003
```
```
1591
```
```
Returns: 1633
```
```
6
```
```
Returns: 121
```
The smallest almost prime number is 11*11 = 121.

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.