| Task | #10 |
|---|---|
| Position | 25 |
| Score | 61,626 |
| Best Score | 2,980 |
| Points | 0.048 |
Problem Statement
You have a data stream of uint32 numbers in binary representation sending to STDIN. The byte order is little endian. Try to find sum (uint64) of all prime numbers for the shortest time.
Numbers quantity is 1 000 000.
Input Generator
The input generator is capped to be int32 instead of uint32, ie I could not find numbers above (2^31 - 1) in the input. distcheck confirms the distribution is uniform in this range.
For testing, we use a random input generator.
Solution Sketch
Did not do anything crazy, just a per-integer miller-rabin check with 2, 7, 61 (if it’s SPRP wrt these numbers, given the range of input it will be prime. Also see SPRP bases)
Thoughts
My number theory sux. That and zielaj’s solution being so impossibly good took away the motivation to grind this problem, because I knew I had no edge. Maybe it’s not about how much edge you have in a problem, but how much you learn from it? Idk. Your solution is probably better than mine.