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
majid, you've hammered so many TLE's, WA's and NZEC's that the 120-submission long SPOJ history doesn't even fully show it, then you switched to CPP and proceeded to hit another 16 WA's and NZEC's before your first AC. I can't even imagine the stupor you find yourself in solving what you consider, as opposed to this, a difficult task, but are you really sure it's the problem that's stupid?
I tried 1000000 ways to solve this STUPID problem in CSHARP but TLE after TLE...
Finally solved it! Nice problem.
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.
|Added by:||Tjandra Satria Gunawan|
|Cluster:||Cube (Intel G860)|
|Languages:||All except: ASM32-GCC ASM64 MAWK BC C-CLANG CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD 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|