## Thursday, July 28, 2016

### Palindromic Primes - GeeksforGeeks

Palindromic Primes - GeeksforGeeks
A palindromic prime (sometimes called a palprime) is a prime number that is also a palindromic number.
Given a number n, print all palindromic primes smaller than or equal to n. For example, If n is 10, the output should be "2, 3, 5, 7′. And if n is 20, the output should be "2, 3, 5, 7, 11′.

`bool` `isPalUtil(``int` `num, ``int``* dupNum)`
`{`
`    ``// Base case (needed for recursion termination):`
`    ``// This statement/ mainly compares the first`
`    ``// digit with the last digit`
`    ``if` `(oneDigit(num))`
`        ``return` `(num == (*dupNum) % 10);`

`    ``// This is the key line in this method. Note`
`    ``// that all recursive/ calls have a separate`
`    ``// copy of num, but they all share same copy`
`    ``// of *dupNum. We divide num while moving up`
`    ``// the recursion tree`
`    ``if` `(!isPalUtil(num/10, dupNum))`
`        ``return` `false``;`

`    ``// The following statements are executed when`
`    ``// we move up the recursion call tree`
`    ``*dupNum /= 10;`

`    ``// At this point, if num%10 contains i'th`
`    ``// digit from beiginning, then (*dupNum)%10`
`    ``// contains i'th digit from end`
`    ``return` `(num % 10 == (*dupNum) % 10);`
`}`

`// The main function that uses recursive function`
`// isPalUtil() to find out whether num is palindrome`
`// or not`
`int` `isPal(``int` `num)`
`{`
`    ``// If num is negative, make it positive`
`    ``if` `(num < 0)`
`       ``num = -num;`

`    ``// Create a separate copy of num, so that`
`    ``// modifications made to address dupNum don't`
`    ``// change the input number.`
`    ``int` `*dupNum = ``new` `int``(num); ``// *dupNum = num`

`    ``return` `isPalUtil(num, dupNum);`
`}`

`// Function to generate all primes and checking`
`// whether number is palindromic or not`
`void` `printPalPrimesLessThanN(``int` `n)`
`{`
`    ``// Create a boolean array "prime[0..n]" and`
`    ``// initialize all entries it as true. A value`
`    ``// in prime[i] will finally be false if i is`
`    ``// Not a prime, else true.`
`    ``bool` `prime[n+1];`
`    ``memset``(prime, ``true``, ``sizeof``(prime));`

`    ``for` `(``int` `p=2; p*p<=n; p++)`
`    ``{`
`        ``// If prime[p] is not changed, then it is`
`        ``// a prime`
`        ``if` `(prime[p] == ``true``)`
`        ``{`
`            ``// Update all multiples of p`
`            ``for` `(``int` `i=p*2; i<=n; i += p)`
`                ``prime[i] = ``false``;`
`        ``}`
`    ``}`

`    ``// Print all palindromic prime numbers`
`    ``for` `(``int` `p=2; p<=n; p++)`

`       ``// checking whether the given number is`
`       ``// prime palindromic or not`
`       ``if` `(prime[p] && isPal(p))`
`          ``cout << p << ``" "``;`
`}`