Prime?

Easy
0/40
Average time to solve is 23m
profile
Contributed by
7 upvotes

Problem statement

Let us call a number prime? if it has exactly two distinct prime divisors. For example, numbers 6, 18, 24 are prime?, while 4, 8, 9, 42 are not. Find the number of prime? numbers which are between 1 and ‘N’, inclusive.

Example : 
‘N’ = 7
 6 is the only prime? number in 1-7. So, the answer is 1.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains a single integer ‘T’ denoting the number of test cases, then the test case follows.

The first line of each test case contains a single integer, ‘N’.
Output Format : 
For each test case, return a single integer, the number of prime? numbers between 1 and ‘N’ (inclusive).

Output for each test case will be printed on a separate line.
Note : 
You are not required to print anything; it has already been taken care of. Just implement the function.
Constraints : 
1 ≤ T ≤ 10
1 ≤ N ≤ 500

Time limit: 1 sec
Sample Input 1 :
2
10
5
Sample Output 1 :
2
0
Explanation For Sample Input 1 :
For the first test case, 6 and 10 are the prime? Numbers. 6 = 3x2 and 10 = 5x2

For the second test case, there are no prime? Numbers till 5.
Sample Input 2:
2
12
20
Sample Output 2 :
3
7
Hint

Since the constraints on ‘N’ are quite small, can we do something like a brute-force?

Approaches (2)
Optimal Approach

Approach: 
 

  • First of all, we will pre-compute which numbers are prime. Since ‘N’ is small enough, we can do this using the naive ‘N.sqrt(N)’ method. (checking primality of each number in sqrt() time).
  • Then, iterate on all numbers from 1 to ‘N’ - call this number ‘A’, and for each ‘A’, check for all of its divisors which ones are prime (this can be done in sqrt(‘A’) time since we can check primality in O(1)).
     

Algorithm: 
 

  • Declare a boolean array ‘isPrime’ of size ‘n+1’, and set it to false initially.
  • Iterate over each number from 2 to ‘n’, call it ‘e’, and for each of those numbers, check if the number is prime or not in sqrt(‘e’) time. If it is prime, set ‘isPrime[e]’ to true.
  • Maintain a variable ‘ans = 0’
  • Maintain a variable ‘cur = 0’
  • Iterate over each number from 1 to ‘n’, call it ‘e’, and for each of those numbers, check for all of its divisors in sqrt(‘e’) time if they are prime or not. For each prime divisor you encounter, increment ‘cur’ by 1. Be careful not to double-count the perfect square root of ‘e’ (if it exists).
  • If ‘cur == 2’, increment ‘ans’ by 1.
  • Reset ‘cur’ to 0.
  • Return ‘ans’
Time Complexity

O(N.sqrt(N)), where ‘N’ is the range given to us.

 

Since we can factorize a number N in sqrt(N) time, we are factorizing every number from 1 to N. Hence the time complexity is O(N.sqrt(N)).

 

Hence, the time complexity is O(N.sqrt(N)).

Space Complexity

O(N), where ‘N’ is the range given to us.

 

We use an array to mark which numbers are prime and which are not.
 

Hence, the space complexity is O(N).

Code Solution
(100% EXP penalty)
Prime?
Full screen
Console