Problem 8

Given a string, find the number of palindromic substring of the string whose length is a prime number. The string consists only of lower case English alphabet. These palindromes need not be distinct.
Note:
1. Palindrome is a string which when reversed is the same. e.g: nitin
2. 1 is not a prime number.

Sample Test Cases:
palindromicPrime ("abac")=1
Explanation: The palindromic substrings in the string are "a", "b", "a", "c" and "aba" but only "aba" is of prime length. So output is 1.

palindromicPrime ("ababac")=4
Explanation: The palindromic substrings in the string are "a", "b", "a", "b", "a", "c", "aba", "aba", "bab" and "ababa". The prime length palindromes are "aba", "aba", "bab" and "ababa". So output is 4. Here we take both "aba" and "aba" as two different palindromes.