Last Updated: 9 Dec, 2022
Prime?
Easy
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.
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
Approaches
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’
Approach:
- Iterate on all numbers from 1 to ‘N’.
- We can prime factorise each number in sqrt() time. We can simply check which numbers have 2 prime factors and increment our answer accordingly.
Algorithm:
- Maintain a variable ‘ans = 0’
- Iterate over each number from 1 to ‘n’, call it ‘e’, and for each of those numbers, prime-factorise it in sqrt(‘e’) time. This can be done by simply checking which numbers divide ‘e’, and then dividing ‘e’ by that number until it is no longer divisible by it, and repeating for the next number. If it was not divisible to begin with, then that number was not a prime factor.
- If the number of prime factors was 2, increment ‘ans’ by 1.
- Return ‘ans’