Count all Prime Length Palindromic Substrings | Python3 implementation of the approach ; Function that returns True if sub - str1ing starting at i and ending at j in str1 is a palindrome ; Function to count all palindromic substr1ing whose lwngth is a prime number ; 0 and 1 are non - primes ; If prime [ p ] is not changed , then it is a prime ; Update all multiples of p greater than or equal to the square of it numbers which are multiple of p and are less than p ^ 2 are already been marked . ; To store the required number of sub - str1ings ; Starting from the smallest prime till the largest Length of the sub - str1ing possible ; If j is prime ; Check all the sub - str1ings of Length j ; If current sub - str1ing is a palindrome ; Driver Code
import math as mt NEW_LINE def isPalindrome ( str1 , i , j ) : NEW_LINE INDENT while ( i < j ) : NEW_LINE INDENT if ( str1 [ i ] != str1 [ j ] ) : NEW_LINE INDENT return False NEW_LINE DEDENT i += 1 NEW_LINE j -= 1 NEW_LINE DEDENT return True NEW_LINE DEDENT def countPrimePalindrome ( str1 , Len ) : NEW_LINE INDENT prime = [ True for i in range ( Len + 1 ) ] NEW_LINE prime [ 0 ] , prime [ 1 ] = False , False NEW_LINE for p in range ( 2 , mt . ceil ( mt . sqrt ( Len + 1 ) ) ) : NEW_LINE INDENT if ( prime [ p ] ) : NEW_LINE INDENT for i in range ( 2 * p , Len + 1 , p ) : NEW_LINE INDENT prime [ i ] = False NEW_LINE DEDENT DEDENT DEDENT count = 0 NEW_LINE for j in range ( 2 , Len + 1 ) : NEW_LINE INDENT if ( prime [ j ] ) : NEW_LINE INDENT for i in range ( Len + 1 - j ) : NEW_LINE INDENT if ( isPalindrome ( str1 , i , i + j - 1 ) ) : NEW_LINE INDENT count += 1 NEW_LINE DEDENT DEDENT DEDENT DEDENT return count NEW_LINE DEDENT s = " geeksforgeeks " NEW_LINE Len = len ( s ) NEW_LINE print ( countPrimePalindrome ( s , Len ) ) NEW_LINE