Timeline for Optimization on Sieve of Eratosthenes using vector<bool>
Current License: CC BY-SA 3.0
19 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 10, 2020 at 13:24 | history | edited | CommunityBot |
Commonmark migration
|
|
| Jan 11, 2016 at 10:47 | history | edited | Deepam Sarmah | CC BY-SA 3.0 |
[Edit removed during grace period]
|
| Dec 3, 2015 at 11:23 | answer | added | DarthGizka | timeline score: 1 | |
| Nov 29, 2015 at 22:17 | comment | added | RBarryYoung | This answer on Stack Overflow contains an extremely optimized sieve implementation with extensive comments. It implements in VB, but should be understandable. Also, it does extra work, because it is actually factoring every number, but you can just remove that part to make it faster. FYI, the principal optimization for the sieve is to implement a "wheel" as explained there... | |
| Nov 29, 2015 at 22:06 | comment | added | 1110101001 | Yea if you can precompute using Mathematica and just stick that into an array it would be better. | |
| Nov 29, 2015 at 20:07 | comment | added | Loki Astari | The best solution to this problem is to first calculate all the primes (upto 1,000,000,000 there are only 50 million (primes.utm.edu/howmany.html)) using another program. Then just have an array of primes that you use in this program. | |
| Nov 29, 2015 at 20:00 | comment | added | Loki Astari | Since 2 and 3 are prime. You can start at 5 and increment by 2,4,2,4,2,4,2,4,2,4,2,4..... for testing (rather than incrementing by 1). | |
| Nov 29, 2015 at 19:59 | comment | added | Loki Astari | Since 2 is a prime. You can start at 3 and increment by 2 for testing (rather than incrementing by 1). | |
| Nov 29, 2015 at 19:58 | comment | added | Loki Astari |
Did nobody mention that the declaration of prime is in the wrong place. By moving it out a level you don't need to re-calculate all the values again and again.
|
|
| Nov 29, 2015 at 19:54 | comment | added | Loki Astari |
Don't use vector<bool> it differs significantly from other containers and is optimized for space not speed. Your code will run much quicker by using vector<char>
|
|
| Nov 29, 2015 at 17:47 | answer | added | JS1 | timeline score: 10 | |
| Nov 29, 2015 at 17:05 | comment | added | Deepam Sarmah | @PeteBecker Thanks for the advice! :) and t stands for the number of test cases. | |
| Nov 29, 2015 at 16:24 | history | edited | 200_success |
edited tags
|
|
| Nov 29, 2015 at 16:14 | history | edited | alexwlchan | CC BY-SA 3.0 |
add a copy of the challenge to the question body
|
| Nov 29, 2015 at 15:35 | answer | added | tejas | timeline score: 2 | |
| Nov 29, 2015 at 15:28 | comment | added | Pete Becker |
Please use meaningful variable names. I think I can guess what t is for, but I really don't want to spend any further time trying to figure out what this code is trying to do.
|
|
| Nov 29, 2015 at 15:24 | history | edited | Jamal | CC BY-SA 3.0 |
deleted 34 characters in body; edited tags; edited title
|
| Nov 29, 2015 at 14:20 | review | First posts | |||
| Nov 29, 2015 at 16:14 | |||||
| Nov 29, 2015 at 14:16 | history | asked | Deepam Sarmah | CC BY-SA 3.0 |