SNGCP - Count Primes

no tags 

Let num(num >= 0) is a positive integer or zero. We can represent num in the following two forms if it is possible to do so -
1. num = n2 + 2 * n, for non-negative integer n
2. num = m2 - 2 * m, for non-negative integer m

Suppose there is num that can be represented in both the forms. Consider this type of number as a magic number. Consider the following 5 cases -
1. n is the only prime.
2. m is the only prime.
3. n and m both are primes.
4. n is prime.
5. m is prime.

Input

First line of input is t, total number of test cases. For each test case the first line is q, total number of queries. Then there will be (2 * q) lines. First line contains c (referring to case mentioned in the problem description) and second line contains two integers a and b defining the range [a, b] for magic number.
t < 1001
q < 5001
0 < c < 6
minimum_value_of_a = 0
maximum_value_of_b = 106

Output

For every test case, that has q queries, the output has (q + 1) lines. First line will be simply printing the test case number and then q lines will be printing total number of magic numbers in the given range [a, b] under the specific case mentioned in input.

Example

Input:
2
3
1
5 20
2
1 30
3
10 18
2
4
1 10
5
1 10
Output: Test Case :#1:
Query :#1: 1
Query :#2: 1
Query :#3: 1

Test Case :#2:
Query :#1: 1
Query :#2: 1

hide comments
David: 2020-04-09 22:11:56

Additional time required for Java to solve the problem. Start up time for the JVM is more than the allowed time limit. This probably also occurs for interpreted languages.

Scape: 2016-03-26 11:06:12

Lame problem

hodobox: 2016-01-18 22:39:31

Can confirm what Andrey said... beware of a>b.

AvmnuSng: 2013-12-04 14:55:31

@NIK : you need to check arrays, you are using to store values, again. Just correct entries in arrays then AC is no where :)

NIK: 2013-12-04 13:00:06

@Abhimanyu,
Plz check ID:10589357
I'm getting wrong answer ,but can't find it even after rigorous debugging.Plz help.
Reply:
@Abhimanyu...Thanks.

Last edit: 2013-12-04 19:49:33
Andrey Maksimenko: 2013-12-01 08:42:51

It is not clear, what is the answer for input:
1
2
2
0 0
5
0 0

because 0 = 0^2-0*0 = 2^2-2*2, so m could be prime, and could be not prime for num=0.

My AC code gives answer "1" for both, so you may assume that for num=0 => m=2.
Also there are strange test cases, where b<a, and you should output 0.

Last edit: 2013-12-01 08:53:51
(^_^): 2013-11-21 06:41:20

can someone provide me more test cases I am getting wrong answer again and again
4
0 1000000
5
0 1000000
3
0 1000000

mehmetin: 2013-11-16 11:22:42

You should consider 0 as a magic number. Problem description is wrong, it should say something like "Let num (num>=0) is a positive or zero integer" in the first line of description. It shouldn't be too hard for the problem setter to change it.

Last edit: 2013-10-19 16:20:40
Piyush Kumar: 2013-11-16 11:22:42

What about 0? First line says num>0, and at the bottom it says minimum_value_of_a = 0.

Last edit: 2013-10-18 20:22:12

Added by:AvmnuSng
Date:2013-09-21
Time limit:0.100s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Abhimanyu Singh
My Problems