AntiprimeNumbers | Topcoder Archive

Problem Statement

In this problem a number is called an antiprime if it does not have any subsequence of digits which is a prime.

For example, 446, 18, and 844 are antiprimes, but 346, 181, and 222 are not. In particular, note that 181 is not an antiprime because its digits contain the subsequence 11 which is a prime.

You are given a String N representing a big integer N. You are also given an int D that is at most 8.

Let X be the number of antiprimes that have exactly N digits and each of those digits is between 1 and D, inclusive. Since X can be very large, compute and return the value (X modulo 1,000,000,007).

Definition

Class:: AntiprimeNumbers
Method:: countAntiPrimes
Parameters:: String, int
Returns:: int
Method signature:: int countAntiPrimes(String N, int D)
(be sure your method is public)

Notes

A positive integer is a prime if it has exactly two positive integer divisors. The smallest few primes are 2, 3, 5, 7, 11, 13, 17, 19, and so on. Notably, the number 1 is not a prime.

Constraints

N will have between 1 and 1,000 characters, inclusive.
Each character of N will be a digit.
The character N[0] will not be '0'.
D will be between 1 and 8, inclusive.

Examples

"61214027451155456631310754220433707056704675307344311"

Returns: 328754822

```
"1"
```
```
5
```
```
Returns: 2
```
We are interested in 1-digit numbers that only use digits 1 through 5. Among those, there are two antiprime numbers: 1 and 4.
```
"2"
```
```
4
```
```
Returns: 2
```
Here the two antiprime numbers are 14 and 44.
```
"2"
```
```
3
```
```
Returns: 0
```
There are no antiprime numbers among the numbers 11, 12, 13, 21, 22, 23, 31, 32, and 33.

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.