Count all Prime Length Palindromic Substrings | Function that returns true if sub - string starting at i and ending at j in str is a palindrome ; Function to count all palindromic substring 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 - strings ; Starting from the smallest prime till the largest length of the sub - string possible ; If j is prime ; Check all the sub - strings of length j ; If current sub - string is a palindrome ; Driver Code
< ? php function isPalindrome ( $ str , $ i , $ j ) { while ( $ i < $ j ) { if ( $ str [ $ i ] != $ str [ $ j ] ) return false ; $ i ++ ; $ j -- ; } return true ; } function countPrimePalindrome ( $ str , $ len ) { $ prime = array_fill ( 0 , $ len + 1 , true ) ; $ prime [ 0 ] = false ; $ prime [ 1 ] = false ; for ( $ p = 2 ; $ p * $ p <= $ len ; $ p ++ ) { if ( $ prime [ $ p ] ) { for ( $ i = $ p * $ p ; $ i <= $ len ; $ i += $ p ) $ prime [ $ i ] = false ; } } $ count = 0 ; for ( $ j = 2 ; $ j <= $ len ; $ j ++ ) { if ( $ prime [ $ j ] ) { for ( $ i = 0 ; $ i + $ j - 1 < $ len ; $ i ++ ) { if ( isPalindrome ( $ str , $ i , $ i + $ j - 1 ) ) $ count ++ ; } } } return $ count ; } $ s = " geeksforgeeks " ; $ len = strlen ( $ s ) ; echo countPrimePalindrome ( $ s , $ len ) ; ? >