Path: csiph.com!news.mixmin.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail From: Tim Rentsch Newsgroups: comp.lang.c++ Subject: Re: Sieve of Erastosthenes optimized to the max Date: Sat, 23 Dec 2023 10:30:21 -0800 Organization: A noiseless patient Spider Lines: 35 Message-ID: <86edfcvkjm.fsf@linuxsc.com> References: MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Injection-Info: dont-email.me; posting-host="a0e2891dc7b8f3c7cc576ac7cc01eb92"; logging-data="2290155"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/Vyi49E7ZSkRyKccDKY/7YbBETR+andEE=" User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux) Cancel-Lock: sha1:33CFMS860q9JZWmmwIjOnWsLbE4= sha1:a3/TSNbwRePKMhi8WOpkGryMJe4= Xref: csiph.com comp.lang.c++:118119 red floyd writes: > On 12/13/2023 7:16 AM, Vir Campestris wrote: > >> On 11/12/2023 17:19, Bonita Montero wrote: >> >>> Am 11.12.2023 um 18:12 schrieb Vir Campestris: >>> >>>> Because all primes except 2 are odd you don't need to store the >>>> _even_ numbers, which is what I meant to say. Or else you only >>>> need to store the odd ones. >>> >>> I'll try that the next days; but I don't expect a significant change. >> >> Well, I went away and tried it. I didn't write anything nearly as >> sophisticated as yours - I didn't worry about threads and >> caching. The code follows. You'll have to unwrap it in a few places. >> >> It occurred to me I could go further - not just optimise it out to >> store odd numbers only, but also miss out the ones divisible by 3, >> or other higher primes. The results were: >> - Storing all numbers: 9.494 seconds to run the sieve >> - Storing odd numbers only: 4.455. That's over twice as fast. >> - Excluding also the ones divisible by 3: 3.468. That's an >> improvement, but not as much as I expected. Perhaps it's got coo >> complicated. I don't have a high powered PC. > > Another way to attempt to optimize is that except for 2 and 3, all > primes are of the form 6n+1 or 6n-1. A more compact form is to consider numbers mod 30, in which case numbers that are 0 mod {2, 3, or 5} can be ignored. Conveniently there are just 8 such values - 1, 7, 11, 13, 17, 19, 23, and 29 - so each block of 30 can be represented in one 8-bit byte. Doing that gives a 25% reduction in space compared to a 6n+/-1 scheme.