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.
|