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):
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...
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.
For each test case, output the number of digit '1' appear in the first N terms of the sequence
50 Output: 2
Unexpected AC with kindof a prototype of a solution. Began thinking about solving this one 3 days ago but didn't like my initial ideas; woke up with better ones and there we go. This is how the best problems work, forcing my brain to work on them even when I don't intend to =)
I was running out of optimizations, but Eratosthenes barely made it through :P
Till: 11753933Last edit: 2016-06-24 15:05:15
@Tjandra Sir can u please tell what improvents can I make in my code or I need to change my brute force approach?
@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.
Wow, @Tjandra, Thanks for this problems. It showed me how I can optimize my Sieve algos.
output of 50 is 47 not 36
(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
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
|Added by:||Tjandra Satria Gunawan|
|Cluster:||Cube (Intel G860)|
|Languages:||All except: ASM32-GCC ASM64 MAWK BC C-CLANG CPP14-CLANG CPP14 COBOL COFFEE D-DMD D-CLANG DART ELIXIR FANTOM FORTH GOSU GRV JS-MONKEY KTLN NIM NODEJS OBJC OBJC-CLANG OCT PICO PROLOG PYPY PY_NBC R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET|