Emirp es la palabra «primo» escrita al revés, y se refiere a un número primo que se convierte en un nuevo número primo cuando inviertes sus dígitos. Emirps no incluye primos palindrómicos (como 151 o 787) ni primos de 1 dígito como 7. 107, 113, 149 y 157: inviértalos y tendrá un nuevo número primo en sus manos. Fuente: wiki
Dado un número n, la tarea es imprimir todos los Emirps menores o iguales a n.
Ejemplos:
Input : n = 40 Output : 13 31 Input : n = 100 Output : 13 31 17 71 37 73 79 97
A continuación se muestran los pasos:
1) Utilice la criba de Eratóstenes para generar todos los números primos menores o iguales que n. También podemos usar tamiz de sundaram .
2) Atraviesa todos los números primos generados. Para cada número primo recorrido, imprima este número y su reverso si se cumplen las siguientes condiciones.
………….a) Si el reverso también es primo.
………….b) El reverso no es igual a primo (no se permiten palíndromos)
………….c) El reverso es menor o igual que n.
A continuación se muestra la implementación de la idea anterior.
C++
//C++ Program to print Emirp numbers less than n
#include <bits/stdc++.h>
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 emirp 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 emirp 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
# 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 emirp 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 emirp 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
<?php
//PHP Program to print Emirp numbers
// less than n
// Function to find reverse
// of any number
function 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)
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 emirp 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
?>
Javascript
<script>
// Javascript program to print Emirp
// numbers less than n
// Function to find reverse of any number
function reverse(x)
{
var rev = 0;
while (x > 0)
{
rev = (rev * 10) + x % 10;
x = parseInt(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.
var prime=Array.from({length: n+1},
(_, i) => true);
for (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 (i = p * 2; i <= n; i += p)
prime[i] = false;
}
}
// Traverse all prime numbers
for (p = 2; p <= n; p++)
{
if (prime[p])
{
// Find reverse a number
var rev = reverse(p);
// A number is emirp if
// it is not a palindrome
// number and its reverse
// is also prime.
if (p != rev && rev <= n &&
prime[rev])
{
document.write(p + " " + rev + " ");
// Mark reverse prime as false
// so that it's
// not printed again
prime[rev] = false;
}
}
}
}
// Driver code
var n = 100;
printEmirp(n);
// This code contributed by Princi Singh
</script>
Producción :
13 31 17 71 37 73 79 97
Este artículo es una contribución de Shivam Pradhan (anuj_charm) . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA