Count Numbers with a Prime Digit Sum
Problem statement
lower and upper are canonical decimal strings representing positive integers L and R. Count the integers x in the inclusive interval [L, R] whose decimal digit sum is prime.
A prime is an integer greater than one with exactly two positive divisors. Return the count as a canonical decimal string so that large inputs and results remain exact.
Function
countPrimeDigitSums(lower: String, upper: String) → StringExamples
Example 1
lower = "1"upper = "20"return = "9"The qualifying numbers are 2, 3, 5, 7, 11, 12, 14, 16, and 20.
Example 2
lower = "98"upper = "102"return = "3"The qualifying numbers are 98, 101, and 102, with digit sums 17, 2, and 3.
Constraints
1 <= L <= R <= 10^18.- Input strings contain only decimal digits and have no leading zeros.
- Use exact integer arithmetic; no modulo is applied.