PrimePalindromic
SRM 303 · 2006-05-18 · by Snail
Problem Statement
A palindrome is a string that reads the same forward and backward. An integer is called prime-palindromic if it is possible to construct a palindrome by concatenating all of its prime factors (without leading zeros). Each prime factor should be used as many times as its power in factorization. In other words if we have an positive integer N = p1w1 * ... * pMwM, where p1...pM are prime factors, then pJ must be used wJ times where J=1..M.
For example, 48 is prime-palindromic because its prime factors are 2, 2, 2, 2, 3 (2 should be used 4 times, 3 should be used once) and we can obtain the palindrome 22322. 2261 is prime-palindromic also because its prime factors are 7, 17, and 19, which can be concatenated to form the palindrome 71917. 2123 is not prime-palindromic because its prime factors are 11 and 193, and neither 11193 nor 19311 are palindromes. 33 is also not prime-palindromic (its prime factors are 3 and 11).
Return the number of prime-palindromic numbers between A and B, inclusive.
Constraints
- A will be between 2 and 10000, inclusive.
- B will be between A and 10000, inclusive.
2260 2262 Returns: 1
The only prime-palindromic number is 2261.
2 9 Returns: 7
All numbers except 6 are prime-palindromic.
2 100 Returns: 36
2 10000 Returns: 728
2 1000 Returns: 175
Submissions are judged against all 28 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class PrimePalindromic with a public method int count(int A, int B) · 28 test cases · 2 s / 256 MB per case