Un primo truncable por la derecha es un primo que sigue siendo primo cuando se elimina sucesivamente el último dígito («derecho»). Por ejemplo, 239 es primo truncable por la derecha ya que 239, 23 y 2 son todos primos. Hay 83 primos truncables por la derecha.
La tarea es comprobar si el número dado (N > 0) es primo truncable por la derecha o no.
Ejemplos:
Input: 239 Output: Yes Input: 101 Output: No 101 is not right-truncatable prime because numbers formed are 101, 10 and 1. Here, 101 is prime but 10 and 1 are not prime.
La idea es generar todos los números primos menores o iguales al número N dado usando la Criba de Eratóstenes . Una vez que hemos generado todos esos números primos, comprobamos si el número sigue siendo primo cuando se elimina sucesivamente el último dígito («derecho»).
C++
//C++ Program to check
// whether a given number
// is right-truncatable
// prime or not.
#include<bits/stdc++.h>
using namespace std;
// Generate all prime numbers less than n.
bool sieveOfEratosthenes(int n, bool isPrime[])
{
// Initialize all entries
// of boolean array as
// true. A value in
// isPrime[i] will finally
// be false if i is Not a
// prime, else true
// bool isPrime[n+1];
isPrime[0] = isPrime[1] = false;
for( int i = 2; i <= n; i++)
isPrime[i] = true;
for (int p = 2; p * p<=n; p++)
{
// If isPrime[p] is not changed, then it is
// a prime
if (isPrime[p] == true)
{
// Update all multiples of p
for (int i = p * 2; i <= n; i += p)
isPrime[i] = false;
}
}
}
// Returns true if n is right-truncatable,
// else false
bool rightTruPrime(int n)
{
// Generating primes using Sieve
bool isPrime[n+1];
sieveOfEratosthenes(n, isPrime);
// Checking whether the number remains
// prime when the last ("right")
// digit is successively removed
while (n)
{
if (isPrime[n])
n = n / 10;
else
return false;
}
return true;
}
// Driver program
int main()
{
int n = 59399;
if (rightTruPrime(n))
cout << "Yes" << endl;
else
cout << "No" << endl;
return 0;
}
Java
// Java code to check
// right-truncatable
// prime or not.
import java.io.*;
class GFG {
// Generate all prime
// numbers less than n.
static void sieveOfEratosthenes
(int n, boolean isPrime[])
{
// Initialize all entries of
// boolean array as true. A
// value in isPrime[i] will
// finally be false if i is
// Not a prime, else true
// bool isPrime[n+1];
isPrime[0] = isPrime[1] = false;
for (int i = 2; i <= n; i++)
isPrime[i] = true;
for (int p=2; p*p<=n; p++)
{
// If isPrime[p] is not
// changed, then it
// is a prime
if (isPrime[p] == true)
{
// Update all multiples of p
for (int i = p * 2; i <= n; i += p)
isPrime[i] = false;
}
}
}
// Returns true if n is
// right-truncatable,
// else false
static boolean rightTruPrime(int n)
{
// Generating primes using Sieve
boolean isPrime[] = new boolean[n+1];
sieveOfEratosthenes(n, isPrime);
// Checking whether the number
// remains prime when the last (right)
// digit is successively removed
while (n != 0)
{
if (isPrime[n])
n = n / 10;
else
return false;
}
return true;
}
// Driver program
public static void main(String args[])
{
int n = 59399;
if (rightTruPrime(n))
System.out.println("Yes");
else
System.out.println("No");
}
}
/* This code is contributed by Nikita Tiwari.*/
Python3
# Python3 Program to check
# whether a given number
# is right-truncatable
# prime or not.
# Generate all prime numbers less than n.
def sieveOfEratosthenes(n,isPrime) :
# Initialize all entries
# of boolean array as
# true. A value in isPrime[i]
# will finally be false if
# i is Not a prime, else true
# bool isPrime[n+1];
isPrime[0] = isPrime[1] = False
for i in range(2, n+1) :
isPrime[i] = True
p = 2
while(p * p <= n) :
# If isPrime[p] is not changed, then it is
# a prime
if (isPrime[p] == True) :
# Update all multiples of p
i = p * 2
while(i <= n) :
isPrime[i] = False
i = i + p
p = p + 1
# Returns true if n is right-truncatable, else false
def rightTruPrime(n) :
# Generating primes using Sieve
isPrime=[None] * (n+1)
sieveOfEratosthenes(n, isPrime)
# Checking whether the
# number remains prime
# when the last ("right")
# digit is successively
# removed
while (n != 0) :
if (isPrime[n]) :
n = n // 10
else :
return False
return True
# Driven program
n = 59399
if (rightTruPrime(n)) :
print("Yes")
else :
print("No")
# This code is contributed by Nikita Tiwari.
C#
// C# code to check right-
// truncatable prime or not
using System;
class GFG {
// Generate all prime
// numbers less than n.
static void sieveOfEratosthenes(int n, bool[] isPrime)
{
// Initialize all entries of
// boolean array as true. A
// value in isPrime[i] will
// finally be false if i is
// Not a prime, else true
// bool isPrime[n+1];
isPrime[0] = isPrime[1] = false;
for (int i = 2; i <= n; i++)
isPrime[i] = true;
for (int p = 2; p * p <= n; p++) {
// If isPrime[p] is not
// changed, then it
// is a prime
if (isPrime[p] == true) {
// Update all multiples of p
for (int i = p * 2; i <= n; i += p)
isPrime[i] = false;
}
}
}
// Returns true if n is right-
// truncatable, else false
static bool rightTruPrime(int n)
{
// Generating primes using Sieve
bool[] isPrime = new bool[n + 1];
sieveOfEratosthenes(n, isPrime);
// Checking whether the number
// remains prime when last (right)
// digit is successively removed
while (n != 0) {
if (isPrime[n])
n = n / 10;
else
return false;
}
return true;
}
// Driven program
public static void Main()
{
int n = 59399;
if (rightTruPrime(n))
Console.WriteLine("Yes");
else
Console.WriteLine("No");
}
}
// This code is contributed by Anant Agarwal
PHP
<?php
// Program to check whether a given number
// is right-truncatable prime or not.
// Generate all prime numbers less than n.
function sieveOfEratosthenes($n, &$isPrime)
{
// Initialize all entries of boolean
// array as true. A value in isPrime[i]
// will finally be false if i is Not a
// prime, else true bool isPrime[n+1];
$isPrime[0] = $isPrime[1] = false;
for ($p = 2; $p * $p <= $n; $p++)
{
// If isPrime[p] is not changed,
// then it is a prime
if ($isPrime[$p] == true)
{
// Update all multiples of p
for ($i = $p * 2; $i <= $n; $i += $p)
$isPrime[$i] = false;
}
}
}
// Returns true if n is right-truncatable,
// else false
function rightTruPrime($n)
{
// Generating primes using Sieve
$isPrime = array_fill(0, $n + 1, true);
sieveOfEratosthenes($n, $isPrime);
// Checking whether the number remains
// prime when the last ("right")
// digit is successively removed
while ($n)
{
if ($isPrime[$n])
$n = (int)($n / 10);
else
return false;
}
return true;
}
// Driver Code
$n = 59399;
if (rightTruPrime($n))
echo "Yes\n";
else
echo "No\n";
// This code is contributed by mits
?>
Javascript
<script>
// javascript code to check
// right-truncatable
// prime or not.
// Generate all prime
// numbers less than n.
function sieveOfEratosthenes(n, isPrime)
{
// Initialize all entries of
// boolean array as true. A
// value in isPrime[i] will
// finally be false if i is
// Not a prime, else true
// bool isPrime[n+1];
isPrime[0] = isPrime[1] = false;
for (let i = 2; i <= n; i++)
isPrime[i] = true;
for (let p = 2; p * p <= n; p++) {
// If isPrime[p] is not
// changed, then it
// is a prime
if (isPrime[p] == true) {
// Update all multiples of p
for (let i = p * 2; i <= n; i += p)
isPrime[i] = false;
}
}
}
// Returns true if n is
// right-truncatable,
// else false
function rightTruPrime(n)
{
// Generating primes using Sieve
let isPrime = new Array(n + 1).fill(false);
sieveOfEratosthenes(n, isPrime);
// Checking whether the number
// remains prime when the last (right)
// digit is successively removed
while (n != 0) {
if (isPrime[n])
n = parseInt(n / 10);
else
return false;
}
return true;
}
// Driver program
var n = 59399;
if (rightTruPrime(n))
document.write("Yes");
else
document.write("No");
// This code is contributed by shikhasingrajput
</script>
Producción:
Yes
Artículo relacionado: Referencias principales truncables por la izquierda : https://en.wikipedia.org/wiki/Truncatable_prime Este artículo es una contribución de Rahul Agrawal . 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