A full prime number is one in which the number itself is prime and all its digits are also prime. Given a number n, check if it is Full Prime or not.
Examples :
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.
The naive approach will be to check if the number is prime or not then check the digits are prime or not, but this won’t be efficient enough.
The efficient method is to do the other way around as there will be very few numbers in every 1000 numbers for which we have to check if it is prime or not, the rest of the numbers will fail when its digits are not prime.
CPP
// CPP program for checking of// full prime#include <bits/stdc++.h>using namespace std;// function to check digitsbool 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 notbool 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 Primeint isFullPrime(int n){ // The order is important here for // efficiency. return (checkDigits(n) && prime(n));}// Driver code to check the above functionint main(){ int n = 53; if (isFullPrime(n)) cout << "Yes"; else cout << "No"; return 0;} |
Java
// Java program for checking// of full primeimport 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 digitsdef 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 notdef 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 Primedef isFullPrime(n) : # The order is important here # for efficiency. return (checkDigits(n) and prime(n))# Driver coden = 53if (isFullPrime(n)) : print("Yes")else : print("No")# This code is contributed by rishabh_jain |
C#
// C# program for checking// of full primeusing 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 digitsfunction 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 notfunction 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 Primefunction 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> |
Output :
Yes
If we are given multiple numbers and range of numbers is small enough so that we can store them in array, we can use Sieve of Eratosthenes to answer queries fast.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
