Question

Prime of Primes
Kavita's teacher wants to test her Mathematics Skills, hence she's given with a number N
erly has to count all the good numbers up to N.
A good number is a number having the following characteristics :
1. It must be a prime number
2. All the Digits in the Good number are also prime.
Example 53 is Good number
Note: 1 and 0 are not Prime numbers
Input Format
Single Integer N
Constraints
1 <= N <= 100000
Output Format​

Answer 1

The problem boils down to finding all the numbers which are prime as well as made up of prime digits.

We first define a function to check if a number is prime. A number is prime if it has no factors other than 1 and itself. So, following a mathematical result, we check the divisibility of the number from 2 to its square root. If a factor is found, the number is not prime. We do not need to check beyond the square root of the number.

We also define a function to check if a number is good. We simply convert the number to a string and check if any non-prime digits are present. If not, we then check if the number is prime using our first function. If it is, the function would return True.

Finally, we take user input of N, and loop through all the numbers from 1 to N, and simply call our function to check if it is a good number or not. We print all good numbers.

$\rule{300}{1}$

Code

from math import sqrt

# Check if a number is prime

def is_prime(n):

   if n < 2:

       return False

   

   # Check division for numbers from 2 to sqrt(n)

   for i in range(2, int(sqrt(n)) + 1):

       if n % i == 0:

           return False

   # If no factor is found, number is prime

   return True

# Check if number is good

def is_good(number):

   # Convert to string for checking non-prime digits

   n = str(number)

   non_prime_digits = ["0", "1", "4", "6", "8", "9"]

   for npd in non_prime_digits:

       # If any non-prime digit is found, return False

       if npd in n:

           return False

   # Check if number is Prime

   if is_prime(number):

       return True

   # Number is not prime. Return False

   return False

# Take user input of N

N = int(input())

# Loop from 1 to N. Print all good numbers

for i in range(1, N + 1):

   if is_good(i):

       print(i)