Timeline for A fast approach to prime number sieving (non-threaded array)
Current License: CC BY-SA 3.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 20, 2014 at 2:27 | comment | added | maaartinus | @AlexLieberman No idea how long it takes... I never used it that big (IIRC I needed just 10e9). For really big primes such sieving isn't efficient. You could easily allocate a 2D array and get up to 1e18 if you had the memory. I'd recommend playing with your code so it gets easy to understand. Write a test (non-exhaustive but fast) and learn some version control (git isn't easy, but it's cool), so you can go back when needed. | |
| Jun 20, 2014 at 2:14 | comment | added | Alex Lieberman | It took one a half week with some occasional hours thereafter. It was for a project my teacher assigned to try to solve a hard algorithm. A modified version of my original code in the link can store in less space, but takes way longer. 270 BIL! Curious as to how long that attempt took. Wish I had this code written in a language that can accept any size and attempt to solve some giant primes. | |
| Jun 20, 2014 at 2:09 | comment | added | maaartinus |
Do you have nothing better to do? :D:D:D As I wrote my sieve some time ago, I spent some time on optimizing it, too, and didn't get this idea. I mostly cared about memory, so I omitted the even numbers and packed bits into a long[] (which allowed me to go up to 270 billion).
|
|
| Jun 20, 2014 at 1:50 | vote | accept | Alex Lieberman | ||
| Jun 20, 2014 at 1:51 | |||||
| Jun 20, 2014 at 1:44 | comment | added | Alex Lieberman | Yes I did. I didn't do a single bit of research actually until it was developed for the most part. I just grabbed a list of numbers and hacked away in Excel for many VERY late nights. I've found some similarities and minor mentions in very few places to some of the steps of the algorithm, but nothing pieced together like this. Thanks for your coding improvement suggestions. | |
| Jun 20, 2014 at 1:36 | history | edited | maaartinus | CC BY-SA 3.0 |
added 1090 characters in body
|
| Jun 20, 2014 at 1:30 | comment | added | maaartinus | @AlexLieberman Glad to hear it... now I was being rather rude. Did you invent the algorithm? | |
| Jun 20, 2014 at 1:29 | history | edited | maaartinus | CC BY-SA 3.0 |
added 1090 characters in body
|
| Jun 20, 2014 at 1:24 | comment | added | Alex Lieberman | True. I appreciate your comments and find them useful :) | |
| Jun 20, 2014 at 1:13 | comment | added | maaartinus | @AlexLieberman There could an error in the opposite direction, too. The full test would take quite long... in the meantime I've verified it against some old code of mine (which is surely correct, as I used it a lot in project Euler). So it's OK, but when I say test, I mean JUnit or whatever running without someone watching the output (it must pass or throw). | |
| Jun 20, 2014 at 1:03 | comment | added | Alex Lieberman | I ran a test of BigInteger.isProbablePrime to print out if false on every index of the boolean array that held true up to N=1,000,000,000. It hung for quite some time (about a minute or two), but didn't print a thing. | |
| Jun 19, 2014 at 23:44 | history | edited | maaartinus | CC BY-SA 3.0 |
added 402 characters in body
|
| Jun 19, 2014 at 22:28 | history | answered | maaartinus | CC BY-SA 3.0 |