Special Primes

Moderate

0/80

Average time to solve is 15m

Contributed by

6 upvotes

Asked in companies

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )

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.

Sample Input 1:

1
5

Sample Output 1:

Explanation for sample input 1:

There are 2 special primes, 2 and 5.
Eg. 1^2 + 1^4 = 2, 2^2 + 1^4 = 5.

Sample Input 2:

1
17

Sample Output 2:

Explanation for sample input 2:

There are 3 special primes 2, 5 and 17.
Eg. 1^2 + 1^4 = 2, 2^2 + 1^4 = 5, 4^2 + 1^4 = 17.

Hint 1

Hint 2

Hint 3

Iterate over all primes and try to find if there exists a pair of values for A and B that form P equals to A^2 + B^4.

Approaches (3)

Approach 1

Approach 2

Approach 3

Naive Solution

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).

Time Complexity

O(N^(7/4)), where N is the given positive integer.

As we are iterating from 1 to N. For each ‘i’ Checking primes take O(N^(½ )) order of time and finding A and B values requires O(N^(¼)) order of time.

Space Complexity

O(1).

We are using constant extra memory.

(100% EXP penalty)

Special Primes

Console