BSPRIME - Binary Sequence of Prime Number
Binary Sequence of Prime Number is a binary sequence that created by converting prime number to base-2 (without leading zeros):
- (2)10=(10)2
- (3)10=(11)2
- (5)10=(101)2
- (7)10=(111)2
- ...
If all base-2 of prime number joined, then we get the binary sequence like this: 10111011111011110110...
Now your task is to count how many digit '1' appear in the first N terms of the sequence, example:
- If N=3, digit '1' appear 2 times: 101110...
- If N=10, digit '1' appear 8 times: 1011101111101...
Input
The first line is an integer T (1 ≤ T ≤ 50,000), denoting the number of test cases. Then, T test cases follow.
For each test case, there is an integer N (0 ≤ N ≤ 150,000,000) written in one line.
Output
For each test case, output the number of digit '1' appear in the first N terms of the sequence
Example
Input: 3 3 10 50 Output: 2 8 36
hide comments
|
Prakhar Gupta:
2014-07-05 06:43:20
any hint???
|
|
[Lakshman]:
2014-05-18 18:28:30
Finally Accepted.!!!!!!!!!! |
|
|
[Lakshman]:
2014-03-30 11:13:57
@Tjandra Satria Gunawan can you please check why I am getting WA, Now I have correct algo with efficient prime computation up to MAX N. |
|
Ehor Nechiporenko:
2013-01-06 20:34:14
Wow, @Tjandra, Thanks for this problems. It showed me how I can optimize my Sieve algos.
|
|
vaibhav:
2013-01-03 06:42:06
output of 50 is 47 not 36
|
|
(Tjandra Satria Gunawan)(曾毅昆):
2012-09-28 10:58:49
Info: Changed cluster to 3GHz and mem limit to 1536 MB. Now 6 users accepted after rejudge. Last edit: 2012-09-28 10:56:16 |
|
himanshu jain:
2012-09-28 10:58:49
how many prime number will be reqd to make 150000000 length string?
|
|
|
Ehor Nechiporenko:
2012-09-28 10:58:49
Good problem, but unfortunantly Atkin Sieve gets TLE (( |
|
Zhouxing Shi:
2012-09-28 10:58:49
nice |
| Added by: | Tjandra Satria Gunawan |
| Date: | 2012-07-12 |
| Time limit: | 1s |
| Source limit: | 10000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All except: ASM32-GCC ASM64 MAWK BC C-CLANG NCSHARP CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JS-MONKEY JULIA KTLN NIM NODEJS OBJC OBJC-CLANG OCT PICO PROLOG PYPY PYPY3 PY_NBC R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET |
| Resource: | Own Problem |
RSS