# Emirp numbers

Emirp is the word “prime” spelled backwards, and it refers to a prime number that becomes a new prime number when you reverse its digits. Emirps do not include palindromic primes (like 151 or 787) nor 1-digit primes like 7. 107, 113, 149, and 157 – reverse them and you’ve got a new prime number on your hands. Source: Wiki

Given a number n, the task is to print all Emrips smaller than or equal to n.
Examples :

```Input  : n = 40
Output : 13 31

Input  : n = 100
Output : 13 31 17 71 37 73 79 97
```

Below are the steps :
1) Use Sieve of Eratosthenes to generate all primes smaller than or equal to n. We can also use sieve of sundaram.

2) Traverse all generated prime numbers. For every traversed prime number print this number and its reverse if following conditions are satisfied.
………….a) If reverse is also prime.
………….b) Reverse is not same as prime (palindromes are not allowed)
………….c) Reverse is smaller than or equal to n.

Below is the implementation of above idea.

## C++

 `// Program to print Emirp numbers less than n ` `#include ` `using` `namespace` `std; ` ` `  `// Function to find reverse of any number ` `int` `reverse(``int` `x) ` `{ ` `    ``int` `rev = 0; ` `    ``while` `(x > 0) ` `    ``{ ` `        ``rev = (rev*10) + x%10; ` `        ``x = x/10; ` `    ``} ` `    ``return` `rev; ` `} ` ` `  `// Sieve method used for generating emirp number ` `// (use of sieve of Eratosthenes) ` `void` `printEmirp(``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``; ` `        ``} ` `    ``} ` ` `  `    ``// Traverse all prime numbers ` `    ``for` `(``int` `p=2; p<=n; p++) ` `    ``{ ` `        ``if` `(prime[p]) ` `        ``{ ` `            ``// Find reverse a number ` `            ``int` `rev = reverse(p); ` ` `  `            ``// A number is emrip if it is not a palindrome ` `            ``// number and its reverse is also prime. ` `            ``if` `(p != rev && rev <= n && prime[rev]) ` `            ``{ ` `               ``cout << p << ``" "` `<< rev << ``" "``; ` ` `  `               ``// Mark reverse prime as false so that it's ` `               ``// not printed again ` `               ``prime[rev] = ``false``; ` `            ``} ` `        ``} ` `    ``} ` `} ` ` `  `// Driver program ` `int` `main() ` `{ ` `    ``int` `n = 40; ` `    ``printEmirp(n); ` `    ``return` `0; ` `} `

## Java

 `// Java program to print Emirp  ` `// numbers less than n ` `import` `java.util.Arrays; ` ` `  `class` `GFG ` `{ ` `    ``// Function to find reverse of any number ` `    ``static` `int` `reverse(``int` `x) ` `    ``{ ` `        ``int` `rev = ``0``; ` `        ``while` `(x > ``0``) ` `        ``{ ` `            ``rev = (rev * ``10``) + x % ``10``; ` `            ``x = x / ``10``; ` `        ``} ` `        ``return` `rev; ` `    ``} ` `     `  `    ``// Sieve method used for generating emirp number ` `    ``// (use of sieve of Eratosthenes) ` `    ``static` `void` `printEmirp(``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. ` `        ``boolean` `prime[]=``new` `boolean``[n + ``1``]; ` `        ``Arrays.fill(prime,``true``); ` `     `  `        ``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``; ` `            ``} ` `        ``} ` `     `  `        ``// Traverse all prime numbers ` `        ``for` `(``int` `p = ``2``; p <= n; p++) ` `        ``{ ` `            ``if` `(prime[p]) ` `            ``{ ` `                ``// Find reverse a number ` `                ``int` `rev = reverse(p); ` `     `  `                ``// A number is emrip if it is not a palindrome ` `                ``// number and its reverse is also prime. ` `                ``if` `(p != rev && rev <= n && prime[rev]) ` `                ``{ ` `                    ``System.out.print(p + ``" "` `+ rev + ``" "``); ` `         `  `                    ``// Mark reverse prime as false so that it's ` `                    ``// not printed again ` `                    ``prime[rev] = ``false``; ` `                ``} ` `            ``} ` `        ``} ` `    ``} ` `     `  `    ``// Driver code ` `    ``public` `static` `void` `main (String[] args) ` `    ``{ ` `        ``int` `n = ``100``; ` `        ``printEmirp(n); ` `    ``} ` `} ` ` `  `// This code is contributed by Anant Agarwal. `

## Python3

 `# Program to print Emirp numbers ` `# less than n ` ` `  `# Function to find reverse  ` `# of any number ` `def` `reverse(x): ` ` `  `    ``rev ``=` `0``; ` `    ``while` `(x > ``0``): ` `        ``rev ``=` `(rev ``*` `10``) ``+` `x ``%` `10``; ` `        ``x ``=` `int``(x ``/` `10``); ` ` `  `    ``return` `rev; ` ` `  `# Sieve method used for generating  ` `# emirp number(use of sieve of  ` `# Eratosthenes) ` `def` `printEmirp(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. ` `    ``prime ``=` `[``1``] ``*` `(n ``+` `1``); ` `    ``p ``=` `2``; ` `    ``while` `(p ``*` `p <``=` `n): ` `         `  `        ``# If prime[p] is not changed, ` `        ``# then it is a prime ` `        ``if` `(prime[p] ``=``=` `1``): ` `             `  `            ``# Update all multiples of p ` `            ``for` `i ``in` `range``(p ``*` `2``, n ``+` `1``, p): ` `                ``prime[i] ``=` `0``; ` `        ``p ``+``=` `1``; ` ` `  `    ``# Traverse all prime numbers ` `    ``for` `p ``in` `range``(``2``, n ``+` `1``): ` `        ``if` `(prime[p] ``=``=` `1``): ` `             `  `            ``# Find reverse a number ` `            ``rev ``=` `reverse(p); ` ` `  `            ``# A number is emrip if it is not  ` `            ``# a palindrome number and its  ` `            ``# reverse is also prime. ` `            ``if` `(p !``=` `rev ``and` `rev <``=` `n ``and` `                       ``prime[rev] ``=``=` `1``): ` `                ``print``(p, rev, end ``=` `" "``); ` `     `  `                ``# Mark reverse prime as  ` `                ``# false so that it's ` `                ``# not printed again ` `                ``prime[rev] ``=` `0``; ` ` `  `# Driver Code ` `n ``=` `100``; ` `printEmirp(n); ` ` `  `# This code is contributed by mits `

## C#

 `// C# program to print Emirp  ` `// numbers less than n ` `using` `System; ` ` `  `class` `GFG ` `{ ` `    ``// Function to find  ` `    ``// reverse of any number ` `    ``static` `int` `reverse(``int` `x) ` `    ``{ ` `        ``int` `rev = 0; ` `        ``while` `(x > 0) ` `        ``{ ` `            ``rev = (rev * 10) + x % 10; ` `            ``x = x / 10; ` `        ``} ` `        ``return` `rev; ` `    ``} ` `     `  `    ``// Sieve method used for ` `    ``// generating emirp number ` `    ``// (use of sieve of Eratosthenes) ` `    ``static` `void` `printEmirp(``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 = ``new` `bool``[n + 1]; ` `        ``for``(``int` `i = 0; i < n + 1; i++) ` `        ``prime[i] = ``true``; ` `     `  `     `  `        ``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``; ` `            ``} ` `        ``} ` `     `  `        ``// Traverse all prime numbers ` `        ``for` `(``int` `p = 2; p <= n; p++) ` `        ``{ ` `            ``if` `(prime[p]) ` `            ``{ ` `                ``// Find reverse a number ` `                ``int` `rev = reverse(p); ` `     `  `                ``// A number is emrip if it  ` `                ``// is not a palindrome number ` `                ``// and its reverse is also prime. ` `                ``if` `(p != rev && rev <= n && prime[rev]) ` `                ``{ ` `                    ``Console.Write(p + ``" "` `+ rev + ``" "``); ` `         `  `                    ``// Mark reverse prime as false  ` `                    ``// so that it's not printed again ` `                    ``prime[rev] = ``false``; ` `                ``} ` `            ``} ` `        ``} ` `    ``} ` `     `  `    ``// Driver code ` `    ``public` `static` `void` `Main () ` `    ``{ ` `        ``int` `n = 100; ` `        ``printEmirp(n); ` `    ``} ` `} ` ` `  `// This code is contributed by nitin mittal. `

## PHP

 ` 0) ` `    ``{ ` `         ``\$rev` `= (``\$rev`  `* 10) + ``\$x` `% 10; ` `        ``\$x` `= (int)(``\$x` `/ 10); ` `    ``} ` `    ``return` `\$rev``; ` `} ` ` `  `// Sieve method used for generating  ` `// emirp number(use of sieve of  ` `// Eratosthenes) ` `function` `printEmirp(``\$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. ` `    ``\$prime` `= ``array_fill``(0, (``\$n` `+ 1), 1); ` ` `  `    ``for` `(``\$p` `= 2; ``\$p` `* ``\$p` `<= ``\$n``; ``\$p``++) ` `    ``{ ` `        ``// If prime[p] is not changed, ` `        ``// then it is a prime ` `        ``if` `(``\$prime``[``\$p``] == 1) ` `        ``{ ` `            ``// Update all multiples of p ` `            ``for` `(``\$i` `= ``\$p` `* 2; ``\$i` `<= ``\$n``; ``\$i` `+= ``\$p``) ` `                ``\$prime``[``\$i``] = 0; ` `        ``} ` `    ``} ` ` `  `    ``// Traverse all prime numbers ` `    ``for` `(``\$p` `= 2; ``\$p` `<= ``\$n``; ``\$p``++) ` `    ``{ ` `        ``if` `(``\$prime``[``\$p``] == 1) ` `        ``{ ` `            ``// Find reverse a number ` `            ``\$rev` `= reverse(``\$p``); ` ` `  `            ``// A number is emrip if it is not  ` `            ``// a palindrome number and its  ` `            ``// reverse is also prime. ` `            ``if` `(``\$p` `!= ``\$rev` `&& ``\$rev` `<= ``\$n` `&&  ` `                ``\$prime``[``\$rev``] == 1) ` `            ``{ ` `                ``echo` `\$p` `. ``" "` `. ``\$rev` `. ``" "``; ` `     `  `                ``// Mark reverse prime as  ` `                ``// false so that it's ` `                ``// not printed again ` `                ``\$prime``[``\$rev``] = 0; ` `            ``} ` `        ``} ` `    ``} ` `} ` ` `  `// Driver Code ` `\$n` `= 100; ` `printEmirp(``\$n``); ` ` `  `// This code is contributed by mits ` `?> `

Output :

```13 31 17 71 37 73 79 97
```