MegaPrime Numbers

Easy
0/40
Average time to solve is 15m
profile
Contributed by
42 upvotes
Asked in companies
Daffodil SoftwareUnthinkable SolutionsNagarro Software

Problem statement

Given two integers ‘Left’ and ‘Right’. Your task is to find the total count of ‘megaprime’ numbers from the range ‘Left’ to ‘Right’. A ‘megaprime’ number is a prime number and its individual digits are also prime.

For example, ‘53’ is a ‘megaprime’ number because ‘53’ is a prime number and its individual digits,‘3’ and ‘5’, are also prime. ‘13’ is not a ‘megaprime’ number because out of its individual digits (1, 3), ‘1’ is not prime.

Note :

1.’Left’ and ‘Right’ both are inclusive in the range ‘Left’ to ‘Right’.

Example :

‘Left’ = ‘23’  and ‘Right’ = ‘37’

binary_heap

All prime numbers from ‘23’ to ‘37’ are 23, 29, 31, 37

23 is ‘megaprime’ number because ‘2’ and ‘3’ both are prime
29 is not ‘megaprime’ number because ‘9’ is not a prime
31 is not a ‘megaprime’ number because ‘1’ is not a prime number
37 is ‘megaprime’ number because ‘3’ and ‘7’ both are prime numbers
Hence there are two ‘megaprime’ numbers 23, 37 out of 23, 29, 31, 37.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of input contains an integer ‘T’ denoting the number of test cases

Next ‘T’ lines contain two space-separated integers ‘Left’ and ‘Right’ which represent the next ‘T’ test cases.
Output Format : 
For each test case, print an integer denoting the total count of ‘megaprime’ numbers.

Note :

You need not to print anything. It has been already taken care of. Just implement the function.
Constraints: 
1 <= T <= 100
1 <= Left <= Right <= 8000

Time Limit: 1 sec
Sample Input 1 :
2
2 15
11 24
Sample Output 1 :
4
1
Explanation Of Sample Input 1 :
Test Case 1:

‘Left’ = ‘2’ and ‘Right’ = ‘15’ 

All prime numbers from ‘2’ to ‘15’ are 2, 3, 5, 7, 11, 13

2 is ‘megaprime’ number because its individual digit ‘2’ is prime.
3 is ‘megaprime’ number because its individual digit ‘3’ is prime.
5 is ‘megaprime’ number because its individual digit ‘5’ is prime.
7 is ‘megaprime’ number because its individual digit ‘7’ is prime.
11 is not ‘megaprime’ number because its individual digits ‘1’ and ‘1’ both are not prime.
13 is not ‘megaprime’ number because its individual digits ‘1’ is not prime.
Hence because there are four ‘megaprime’ numbers 2, 3, 5, 7 out of 2, 3, 5, 7, 11, 13, we return four.


Test case 2:


‘Left’ = 11 and ‘Right’ = 24 

All prime numbers from ‘11’ to ‘24’ are 11, 13, 17, 19, 23

11 is not a ‘megaprime’ number because its individual digit ‘1’ is not prime.
13 is not ‘megaprime’ number because its individual digit ‘1’ is not prime.
17 is not ‘megaprime’ number because its individual digit ‘1’ is not prime.
19 is not ‘megaprime’ number because its individual digits ‘1’ and ‘9’ both are not prime.
23 is ‘megaprime’ number because its individual digits ‘2’ and ‘3’ both are prime.

Since there is only one ‘megaprime’ number, 23 out of 11 13, 17, 19, 23, we return one.
Sample Input 2 :
2
1 11
1 100
Sample Output 2 :
4
8
Hint

Try to check every number in range if it is prime or not. 

Approaches (3)
Brute Force

The idea is to check every number from ‘Left’ to ‘Right’ whether it is prime or not. If the number isprime, then check for its individual digits.

  • This is a Naive/Brute Force approach
  • Take a variable ‘count’ to track the total number of ‘megaprime’ numbers and initialize the ‘count’ variable to ‘0’
  • Iterate a loop where ‘i’ ranges from ‘Left’ to ‘Right’
  • For every ‘i’,check if ‘i’ is prime or not
    • To check whether ‘i’ is prime or not
      • Iterate ‘j’ from ‘2’ to ‘i-1’
      • If at any point, ‘i%2 becomes equal to 0’
        • Then ‘i’ is not prime
        • Else ‘i’ is prime
    • If ‘i’ is prime, then check for its individual digits
      • To check individual digits of ‘i’, whether they are prime or not
      • First copy ‘i’ in a variable ‘num’
      • Then iterate ‘num’ until it’s not ‘0’
        • Check for every digit with of ‘num’.
        • If ‘num%10’ is prime then check for the next digit, otherwise as the condition of every digit being a prime is not fulfilled, jump out of the loop.
        • Then update ‘num = num/10’
    • If all individual digits of  ‘i’ are prime then increase ‘count’ by ‘1’
  • In the end, return ‘count’
Time Complexity

O(N^2*log(N)), Where ‘N’ is the total number from ‘Left’ to ‘Right’.

 

We are checking for every number is prime or not in O(N) time and if any number is prime then check for its all digits, any number can have log(N) digits. So total time is required ‘N*N*log(N)’.

Space Complexity

O(1).

 

As we are using constant space.

Code Solution
(100% EXP penalty)
MegaPrime Numbers
Full screen
Console