Un primo truncable por la izquierda es un primo que en una base dada (por ejemplo, 10) no contiene 0 y que sigue siendo primo cuando se elimina sucesivamente el dígito inicial («izquierdo»). Por ejemplo, 317 es primo truncable por la izquierda ya que 317, 17 y 7 son todos primos. Hay un total de 4260 números primos truncables por la izquierda.
La tarea es verificar si el número dado (N > 0) es primo truncable por la izquierda o no.
Ejemplos:
Input: 317 Output: Yes Input: 293 Output: No 293 is not left-truncatable prime because numbers formed are 293, 93 and 3. Here, 293 and 3 are prime but 93 is not prime.
La idea es verificar primero si el número contiene 0 como dígito o no y contar el número de dígitos en el número N dado. Si contiene 0, devolver falso; de lo contrario, generar todos los primos menores o iguales al número N dado usando Tamiz de Eratóstenes. . Una vez que hemos generado todos esos primos, comprobamos si el número sigue siendo primo cuando se elimina sucesivamente el dígito inicial («izquierdo»).
A continuación se muestra la implementación del enfoque anterior.
C++
// Program to check whether a given number
// is left-truncatable prime or not.
#include<bits/stdc++.h>
using namespace std;
/* Function to calculate x raised to the power y */
int power(int x, unsigned int y)
{
if (y == 0)
return 1;
else if (y%2 == 0)
return power(x, y/2)*power(x, y/2);
else
return x*power(x, y/2)*power(x, y/2);
}
// 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 leftTruPrime(int n)
{
int temp = n, cnt = 0, temp1;
// Counting number of digits in the
// input number and checking whether it
// contains 0 as digit or not.
while (temp)
{
cnt++; // counting number of digits.
temp1 = temp%10; // checking whether digit is 0 or not
if (temp1==0)
return false; // if digit is 0, return false.
temp = temp/10;
}
// Generating primes using Sieve
bool isPrime[n+1];
sieveOfEratosthenes(n, isPrime);
// Checking whether the number remains prime
// when the leading ("left") digit is successively
// removed
for (int i=cnt; i>0; i--)
{
// Checking number by successively removing
// leading ("left") digit.
/* n=113, cnt=3
i=3 mod=1000 n%mod=113
i=2 mod=100 n%mod=13
i=3 mod=10 n%mod=3 */
int mod= power(10,i);
if (!isPrime[n%mod]) // checking prime
return false; // if not prime, return false
}
return true; // if remains prime, return true
}
// Driver program
int main()
{
int n = 113;
if (leftTruPrime(n))
cout << n << " is left truncatable prime" << endl;
else
cout << n << " is not left truncatable prime" << endl;
return 0;
}
Java
// Program to check whether
// a given number is left
// truncatable prime or not.
import java.io.*;
class GFG {
// Function to calculate x
// raised to the power y
static int power(int x,int y)
{
if (y == 0)
return 1;
else if (y%2 == 0)
return power(x, y/2)
*power(x, y/2);
else
return x*power(x, y/2)
*power(x, y/2);
}
// 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 leftTruPrime(int n)
{
int temp = n, cnt = 0, temp1;
// Counting number of digits in the
// input number and checking whether
// it contains 0 as digit or not.
while (temp != 0)
{
// counting number of digits.
cnt++;
temp1 = temp%10;
// checking whether digit is
// 0 or not
if (temp1 == 0)
return false;
temp = temp/10;
}
// Generating primes using Sieve
boolean isPrime[] = new boolean[n+1];
sieveOfEratosthenes(n, isPrime);
// Checking whether the number
// remains prime when the leading
// ("left") digit is successively removed
for (int i = cnt; i > 0; i--)
{
// Checking number by successively
// removing leading ("left") digit.
/* n=113, cnt=3
i=3 mod=1000 n%mod=113
i=2 mod=100 n%mod=13
i=3 mod=10 n%mod=3 */
int mod = power(10,i);
if (!isPrime[n%mod])
return false;
}
// if remains prime, return true
return true;
}
// Driver program
public static void main(String args[])
{
int n = 113;
if (leftTruPrime(n))
System.out.println
(n+" is left truncatable prime");
else
System.out.println
(n+" is not left truncatable prime");
}
}
/*This code is contributed by Nikita Tiwari.*/
Python3
# Python3 Program to
# check whether a
# given number is left
# truncatable prime
# or not.
# Function to calculate
# x raised to the power y
def power(x, y) :
if (y == 0) :
return 1
elif (y % 2 == 0) :
return(power(x, y // 2) *
power(x, y // 2))
else :
return(x * power(x, y // 2) *
power(x, y // 2))
# 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 leftTruPrime(n) :
temp = n
cnt = 0
# Counting number of
# digits in the input
# number and checking
# whether it contains
# 0 as digit or not.
while (temp != 0) :
# counting number
# of digits.
cnt=cnt + 1
# checking whether
# digit is 0 or not
temp1 = temp % 10;
if (temp1 == 0) :
# if digit is 0,
# return false.
return False
temp = temp // 10
# Generating primes
# using Sieve
isPrime = [None] * (n + 1)
sieveOfEratosthenes(n, isPrime)
# Checking whether the
# number remains prime
# when the leading
# ("left") digit is
# successively removed
for i in range(cnt, 0, -1) :
# Checking number by
# successively removing
# leading ("left") digit.
# n=113, cnt=3
# i=3 mod=1000 n%mod=113
# i=2 mod=100 n%mod=13
# i=3 mod=10 n%mod=3
mod = power(10, i)
# checking prime
if (isPrime[n % mod] != True) :
# if not prime,
# return false
return False
# if remains prime
# , return true
return True
# Driver program
n = 113
if (leftTruPrime(n)) :
print(n, "is left truncatable prime")
else :
print(n, "is not left truncatable prime")
# This code is contributed by Nikita Tiwari.
C#
// Program to check whether
// a given number is left
// truncatable prime or not.
using System;
class GFG {
// Function to calculate x
// raised to the power y
static int power(int x, int y)
{
if (y == 0)
return 1;
else if (y%2 == 0)
return power(x, y/2)
*power(x, y/2);
else
return x*power(x, y/2)
*power(x, y/2);
}
// 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 leftTruPrime(int n)
{
int temp = n, cnt = 0, temp1;
// Counting number of digits in the
// input number and checking whether
// it contains 0 as digit or not.
while (temp != 0)
{
// counting number of digits.
cnt++;
temp1 = temp%10;
// checking whether digit is
// 0 or not
if (temp1 == 0)
return false;
temp = temp/10;
}
// Generating primes using Sieve
bool []isPrime = new bool[n+1];
sieveOfEratosthenes(n, isPrime);
// Checking whether the number
// remains prime when the leading
// ("left") digit is successively removed
for (int i = cnt; i > 0; i--)
{
// Checking number by successively
// removing leading ("left") digit.
/* n=113, cnt=3
i=3 mod=1000 n%mod=113
i=2 mod=100 n%mod=13
i=3 mod=10 n%mod=3 */
int mod = power(10, i);
if (!isPrime[n%mod])
return false;
}
// if remains prime, return true
return true;
}
// Driver program
public static void Main()
{
int n = 113;
if (leftTruPrime(n))
Console.WriteLine
(n + " is left truncatable prime");
else
Console.WriteLine
(n + " is not left truncatable prime");
}
}
//This code is contributed by Anant Agarwal.
PHP
<?php
// PHP Program to check whether a
// given number is left-truncatable
// prime or not.
/* Function to calculate x raised to
the power y */
function power($x, $y)
{
if ($y == 0)
return 1;
else if ($y % 2 == 0)
return power($x, $y/2) *
power($x, $y/2);
else
return $x*power($x, $y/2) *
power($x, $y/2);
}
// Generate all prime numbers
// less than n.
function sieveOfEratosthenes($n, $l,
$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] = -1;
for ($i = 2; $i <= $n; $i++)
$isPrime[$i] = true;
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 leftTruPrime($n)
{
$temp = $n; $cnt = 0; $temp1;
// Counting number of digits in
// the input number and checking
// whether it contains 0 as digit
// or not.
while ($temp)
{
// counting number of digits.
$cnt++;
// checking whether digit is
// 0 or not
$temp1 = $temp % 10;
if ($temp1 == 0)
// if digit is 0, return
// false.
return -1;
$temp = $temp / 10;
}
// Generating primes using Sieve
$isPrime[$n + 1];
sieveOfEratosthenes($n, $isPrime);
// Checking whether the number
// remains prime when the leading
// ("left") digit is successively
// removed
for ($i = $cnt; $i > 0; $i--)
{
// Checking number by
// successively removing
// leading ("left") digit.
/* n=113, cnt=3
i=3 mod=1000 n%mod=113
i=2 mod=100 n%mod=13
i=3 mod=10 n%mod=3 */
$mod= power(10, $i);
// checking prime
if (!$isPrime[$n % $mod])
// if not prime, return
// false
return -1;
}
// if remains prime, return true
return true;
}
// Driver program
$n = 113;
if (leftTruPrime($n))
echo $n, " is left truncatable",
" prime", "\n";
else
echo $n, " is not left ",
"truncatable prime", "\n";
// This code is contributed by ajit
?>
Javascript
<script>
// Javascript program to check whether
// a given number is left
// truncatable prime or not.
function power(x, y)
{
if (y == 0)
return 1;
else if (y%2 == 0)
return power(x, Math.floor(y/2))
*power(x, Math.floor(y/2));
else
return x*power(x, Math.floor(y/2))
*power(x, Math.floor(y/2));
}
// 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 leftTruPrime(n)
{
let temp = n, cnt = 0, temp1;
// Counting number of digits in the
// input number and checking whether
// it contains 0 as digit or not.
while (temp != 0)
{
// counting number of digits.
cnt++;
temp1 = temp%10;
// checking whether digit is
// 0 or not
if (temp1 == 0)
return false;
temp = Math.floor(temp/10);
}
// Generating primes using Sieve
let isPrime = Array.from({length: n+1}, (_, i) => 0);
sieveOfEratosthenes(n, isPrime);
// Checking whether the number
// remains prime when the leading
// ("left") digit is successively removed
for (let i = cnt; i > 0; i--)
{
// Checking number by successively
// removing leading ("left") digit.
/* n=113, cnt=3
i=3 mod=1000 n%mod=113
i=2 mod=100 n%mod=13
i=3 mod=10 n%mod=3 */
let mod = power(10,i);
if (!isPrime[n%mod])
return false;
}
// if remains prime, return true
return true;
}
// Driver Code
let n = 113;
if (leftTruPrime(n))
document.write
(n+" is left truncatable prime");
else
document.write
(n+" is not left truncatable prime");
// This code is contributed by sanjoy_62.
</script>
Producción:
113 is left truncatable prime
Complejidad en el peor de los casos: O(N*N)
Artículo relacionado: Referencias
principales truncables a la derecha : 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