AntiprimeNumbers
SRM 772 · 2019-12-10 · by abdullahkool768
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
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).
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.
"608478" 8 Returns: 397463353
"183" 8 Returns: 573571367
"220" 2 Returns: 0
"1" 1 Returns: 1
"50114" 7 Returns: 823979831
"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.
Submissions are judged against all 210 archived test cases, of which 8 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class AntiprimeNumbers with a public method int countAntiPrimes(string N, int D) · 210 test cases · 2 s / 256 MB per case