Un número primo completo es aquel en el que el número en sí es primo y todos sus dígitos también son primos. Dado un número n, verifique si es Full Prime o no.
Ejemplos:
Input : 53 Output : Yes Explanation: Number 53 is prime and its digits are also prime. Input : 41 Output : No Explanation: Number 41 is prime but its digits are not prime.
El enfoque ingenuo será verificar si el número es primo o no y luego verificar si los dígitos son primos o no, pero esto no será lo suficientemente eficiente.
El método eficiente es hacerlo al revés, ya que habrá muy pocos números de cada 1000 números para los que tenemos que comprobar si es primo o no, el resto de los números fallarán cuando sus dígitos no sean primos.
CPP
// CPP program for checking of
// full prime
#include <bits/stdc++.h>
using namespace std;
// function to check digits
bool checkDigits(int n)
{
// check all digits are prime or not
while (n) {
int dig = n % 10;
// check if digits are prime or not
if (dig != 2 && dig != 3 &&
dig != 5 && dig != 7)
return false;
n /= 10;
}
return true;
}
// To check if n is prime or not
bool prime(int n)
{
if (n == 1)
return false;
// check for all factors
for (int i = 2; i * i <= n; i++) {
if (n % i == 0)
return false;
}
return true;
}
// To check if n is Full Prime
int isFullPrime(int n)
{
// The order is important here for
// efficiency.
return (checkDigits(n) && prime(n));
}
// Driver code to check the above function
int main()
{
int n = 53;
if (isFullPrime(n))
cout << "Yes";
else
cout << "No";
return 0;
}
Java
// Java program for checking
// of full prime
import java.util.*;
class Prime{
// function to check digits
public static boolean checkDigits(int n)
{
// check all digits are prime or not
while (n > 0) {
int dig = n % 10;
// check if digits are prime or not
if (dig != 2 && dig != 3 &&
dig != 5 && dig != 7)
return false;
n /= 10;
}
return true;
}
// To check if n is prime or not
public static boolean prime(int n)
{
if (n == 1)
return false;
// check for all factors
for (int i = 2; i * i <= n; i++) {
if (n % i == 0)
return false;
}
return true;
}
// To check if n is Full Prime
public static boolean isFullPrime(int n)
{
// The order is important here for
// efficiency
return (checkDigits(n) && prime(n));
}
// driver code
public static void main(String[] args)
{
int n = 53;
if (isFullPrime(n))
System.out.print( "Yes" );
else
System.out.print( "No");
}
}
// This code is contributed by rishabh_jain
Python
# Python program for checking
# of full prime
# function to check digits
def checkDigits(n):
# check all digits are
# prime or not
while (n) :
dig = n % 10
# check if digits are
# prime or not
if (dig != 2 and
dig != 3 and dig != 5
and dig != 7) :
return 0
n = n / 10
return 1
# To check if n is prime or not
def prime(n):
if (n == 1):
return 0
# check for all factors
i = 2
while i * i <= n :
if (n % i == 0):
return 0
i = i + 1
return 1
# To check if n is Full Prime
def isFullPrime(n) :
# The order is important here
# for efficiency.
return (checkDigits(n) and prime(n))
# Driver code
n = 53
if (isFullPrime(n)) :
print("Yes")
else :
print("No")
# This code is contributed by rishabh_jain
C#
// C# program for checking
// of full prime
using System;
class Prime
{
// function to check digits
public static bool checkDigits(int n)
{
// check all digits are prime or not
while (n > 0) {
int dig = n % 10;
// check if digits are prime or not
if (dig != 2 && dig != 3 &&
dig != 5 && dig != 7)
return false;
n /= 10;
}
return true;
}
// To check if n is prime or not
public static bool prime(int n)
{
if (n == 1)
return false;
// check for all factors
for (int i = 2; i * i <= n; i++) {
if (n % i == 0)
return false;
}
return true;
}
// To check if n is Full Prime
public static bool isFullPrime(int n)
{
// The order is important here for
// efficiency
return (checkDigits(n) && prime(n));
}
// Driver code
public static void Main()
{
int n = 53;
if (isFullPrime(n))
Console.WriteLine( "Yes" );
else
Console.WriteLine( "No");
}
}
// This code is contributed by vt_m
PHP
<?php
// PHP program for checking
// of full prime
// function to check digits
function checkDigits($n)
{
// check all digits
// are prime or not
while ($n)
{
$dig = $n % 10;
// check if digits are
// prime or not
if ($dig != 2 && $dig != 3 &&
$dig != 5 && $dig != 7)
return false;
$n = (int)($n / 10);
}
return true;
}
// To check if n is prime or not
function prime($n)
{
if ($n == 1)
return false;
// check for all factors
for ($i = 2; $i * $i <= $n; $i++)
{
if ($n % $i == 0)
return false;
}
return true;
}
// To check if n is Full Prime
function isFullPrime($n)
{
// The order is important
// here for efficiency.
return (checkDigits($n) &&
prime($n));
}
// Driver Code
$n = 53;
if (isFullPrime($n))
echo("Yes");
else
echo("No");
// This code is contributed by Ajit.
?>
Javascript
<script>
// Javascript program for checking of full prime
// function to check digits
function checkDigits(n)
{
// check all digits are prime or not
while (n > 0) {
let dig = n % 10;
// check if digits are prime or not
if (dig != 2 && dig != 3 &&
dig != 5 && dig != 7)
return false;
n = parseInt(n / 10, 10);
}
return true;
}
// To check if n is prime or not
function prime(n)
{
if (n == 1)
return false;
// check for all factors
for (let i = 2; i * i <= n; i++) {
if (n % i == 0)
return false;
}
return true;
}
// To check if n is Full Prime
function isFullPrime(n)
{
// The order is important here for
// efficiency
return (checkDigits(n) && prime(n));
}
let n = 53;
if (isFullPrime(n))
document.write( "Yes" );
else
document.write( "No");
</script>
Producción :
Yes
Si nos dan varios números y el rango de números es lo suficientemente pequeño como para que podamos almacenarlos en una array, podemos usar Sieve of Eratosthenes para responder consultas rápidamente.