Last Updated: 27 Nov, 2020

MegaPrime Numbers

Easy

Asked in companies

Solve now

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.

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

Solve now

Approaches

01 Approach

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’

Solve now

02 Approach

The idea is to pre-compute whether the numbers from ‘1’ to ‘Right’ ( given second integer ) are prime or not, so that we need not check the number for being prime or not, every time.

To pre-compute, we use this approach
Use a list of size ‘Right’ initialize it to ‘True’ and called it ‘primeArr’
Initially, consider ‘K’ equals 2, which is the first prime number
Iterate from ‘K’^2 to ‘Right’, we are iterating from ‘K^2’ because it is sure that we have already marked all prime of not prime numbers that are less than ‘K^2’ in the previous iteration.
- If ‘primeArr[K]’ is ‘True’ then all the multiples of ‘K’ will be non-prime
- So we assign all multiples of ‘K’ to non-prime with ‘primeArr[X]’= ‘False’, Where ‘X’ is multiple of ‘K’.
- Then increase the value of ‘K’ by ‘1’
Iterate ‘K’ for the next value.
In the end, we will get a ‘primeArr’ in which ‘primeArr[i]’ will represent whether ‘i’ is prime or not
- If ‘i’ is prime, then the value of ‘primeArr[i] will be ‘True’
- Else value of ‘primeArr[i]’ will ‘False’
After generating ‘primeArr’ we can find all megaprime numbers by a single iteration
Iterate ‘i’ loop from ‘Left’ to ‘Right’
- Check whether ‘i’ is prime or not in 0(1) time with help of ‘primeArr’
  - If ‘i’ is prime then check for its individual digits.
Use this ‘primeArr’ for all the test cases and we don’t need to generate this for each test case.

Solve now

03 Approach

In this approach, we try to modify the ‘Sieve of Eratosthenes algorithm’. For every number ‘i’ where ‘i’ is 2 to ‘Right-1’, check if ‘i’ is prime or not. If yes, then store it into ‘primeArr’. For every prime number ‘j’ and ‘j’ is less than or equal to the smallest prime factor ‘p’ of ‘i’. Mark all numbers ‘j*p’ to non-prime.

To implement this approach we need three list
- isPrime - isPrime[i] tell us ‘i’ is prime or not and initially every number is prime
- prime - store all prime numbers less than ‘Right’
- smallestPrimeFactor - smallestPrimeFactor[i] tell us smallest prime factor of ‘i’
Make sure isPrime[0] and isPrime[1] both are ‘False’
Iterate ‘i’ from ‘2’ to ‘Right-1’
- If ‘isPrime[i]’ is ‘True’ then
  - Add ‘i’ in ‘prime’ and ‘smallestPrimeFactor[i] = i’
  - It is clear that all the multiple of ‘i’ will be non-prime
- Use ‘j’ to do the above task
  - ‘isPrime[i * prime[j]] = False’
  - ‘smallestPrimeFactor[i] = prime[j]’
  - Check for next ‘j’
Iterate ‘i’ for the next value.
In the end, we will get an ‘isPrime’ in which ‘isPrime[i]’ will represent ‘i’ is prime or not
- If ‘i’ is prime then the value of ‘isPrime[i]’ will ‘True’
- Else value of ‘isPrime[i]’ will ‘False’
After generating ‘isPrime[i]’ we can find all ‘megaprime’ number by a single iteration
Iterate ‘i’ loop from‘Left’ to ‘Right’
- Check ‘i’ is prime or not in 0(1) time with help of ‘isPrime’
  - If ‘i’ is prime then check for its individual digit.
Use this ‘isPrime’ for all the test cases and we don’t need to generate this for each test case.

Solve now