SPCO - Gopu and Counting Bitwise Prime Numbers
A positive integer is said to be Bit-sum-prime if the sum of all the bits in
its binary representation is a prime number
A positive integer is said to be bitwise prime if the sum of all the bits in its binary representation is a prime number.
You are given two integers a and b. You have to output number of bitwise prime numbers between a and b (inclusive).
Input
First line contains T : number of test cases. (1 <= T <= 10^5)
For next T lines, each test case contains two space seperated integers a and b. (a <= b). 1 <= a, b <= 10^19.
Output
For each test case, print the number of bitwise prime numbers between a and b (inclusive).
Example
Input: 2
1 2
1 3 Output: 0
1
hide comments
Mitch Schwartz:
2014-01-20 01:59:26
This is very similar to some other problems on SPOJ, but I think it's ok to keep in classical for speed comparison as the constraints are higher. Last edit: 2014-01-12 18:00:14 |
Added by: | praveen123 |
Date: | 2013-12-23 |
Time limit: | 3s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | IITK ACA CSE online judge |