Last Updated: 16 Dec, 2020
Special Primes
Moderate
Asked in companies
You are given an integer N, and you need to find the number of Special Primes smaller than or equal to N.
Note:
1. A Prime number is a number that has only two factors 1 and N itself.
2. A Prime number P is known as Special Prime if it can
be represented as follows:
P = A^2 + B^4
where A and B are positive integers.
3. A and B should be greater than 0.
Input Format:
The first line of the input contains an integer 'T' denoting the number of test cases.
The first and only line of each test case consists of a single positive integer 'N'.
Output Format:
For each test case, print an integer that denotes the count of the number of Special Primes smaller than or equal to 'N' in a separate line.
The output of each test case should be printed in a separate line.
Note:
You don't have to print anything, and it has already been taken care of. Just Implement the given function.
Constraints:
1 <= T <= 100
1 <= N <= 5 * 10^5
Where 'T' represents the number of test cases, and 'N' is the given number.
Time Limit: 1 sec.
Approaches
- Iterate from 1 to N.
- Check if the current integer, let's say ‘I’ is prime or not.
- If ‘I’ is prime, then try to find if we can represent ‘I’ as follows:
- I = A^2 + B^4.
- For checking ‘I’ is Special Prime or not, do the following steps:
- Try values of B from 1 till B^4 <=N
- Subtract B^4 from ‘I’.
- Check if I - B^4 is a perfect square number or not.
- If (floor(sqrt(I - B^4)))^2 == I - B^4 then I - B^4 is a perfect square number.
- If it is a perfect square, then ‘I’ is a Special Prime.
- If we can then, we need to increment specialPrimesCount for each such ‘I’. And we get our required number of Special Primes in the range 1 to N.
- To check whether ‘I’ is prime or not, we can try to find a factor of I in the range 2 to sqrt(I).
- Iterate from 1 to N.
- Check if the current integer, let's say ‘I’ is prime or not.
- If ‘I’ is prime, then try to find if we can represent 'I' as follows:
- I = A^2 + B^4.
- For checking ‘I’ is Special Prime or not, do the following steps:
- Try values of B from 1 till B^4 <=N
- Subtract B^4 from ‘I’.
- Check if I - B^4 is a perfect square number or not.
- if (floor(sqrt(I - B^4)))^2 == I - B^4 then I - B^4 is a perfect square number.
- If it is a perfect square, then ‘I’ is a Special Prime.
- If we can then, we need to increment specialPrimesCount for each such ‘I’. And we get our required number of Special Primes in the range 1 to N.
- To check, ‘I’ is prime or not, we can pre-calculate all the primes in the range 1 to N by using Sieve of Eratosthenes in O(Nlog(logN)) time complexity.
- Mark all the prime numbers in the range 1 to N, using Sieve of Eratosthenes in O(Nlog(logN)) order time.
- Store all possible A^2 and B^4 values which are less than or equal to N.
- Run a loop from 1 to square root of N (with loop variable i), and store i^2 in a vector say A(if the value is less than N) and i^4 in another vector, say B(if the value is less than N).
- Try all possible combinations of A^2 and B^4.
- If A^2 + B^4 is a prime number and also it is not included so far, increment specialPrimesCount and mark this A^2 + B^4 so that it won’t be considered again in the specialPrimeCount.
Similar problems