Path: csiph.com!news.swapon.de!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: Mon, 01 Jul 2024 23:20:27 -0700 Organization: A noiseless patient Spider Lines: 35 Message-ID: <86zfr0b9hw.fsf@linuxsc.com> References: <86r0duwqgg.fsf@linuxsc.com> <86o78mpnlf.fsf@linuxsc.com> <86ttibod7n.fsf@linuxsc.com> <86h6eaoi2r.fsf@linuxsc.com> <867celixcw.fsf@linuxsc.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Injection-Date: Tue, 02 Jul 2024 08:20:29 +0200 (CEST) Injection-Info: dont-email.me; posting-host="a921cf177a5ef0d729c498a18e4544b7"; logging-data="1587762"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/RbBCLuVjgMk5PIoeNxRUiVrzyBWaD9Ko=" User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux) Cancel-Lock: sha1:J6/kSaVNjjg/p05QpzS4NoDiHds= sha1:FVd2iftATGWxib4IhyDMnpSRWO0= Xref: csiph.com comp.lang.c++:119596 Vir Campestris writes: > On 19/06/2024 01:34, Tim Rentsch wrote: > >> Would you mind if I asked you to post the code so I can >> take a look at it? Or if you would rather email it to >> me that also works. > > I've hacked out all my include files, added a GPL licence, and > included build instructions. It follows in the signature block. > 600 lines :( > > I bet the line wrapping breaks it too. I got the code. There were some line wrappings but I just went through and fixed those by hand. After fixing the problem line wraps I was able to compile and run the code (I used std=c++17, which apparently works okay). I did a simple check to make sure the primes being found are right, which they do indeed seem to be. I haven't really experimented with changing the code; I only just ran it with various bounds on what primes to find, mostly to get a sense of the performance. I admit I don't understand the scheme the code is using. It looks to me like the code is doing divisions and remainders a lot, which my code basically doesn't do at all (it does do one division for each prime up to the square root of the limit of primes being sought, but that's all). I know the big template near the beginning is crucial to understanding what the code is doing, but I haven't been able to figure out what abstraction that template is supposed to represent. The core of my program is between 50 and 60 lines, and all pretty straightforward. Is there some suggestion you could make or a question you would like to ask? What can I do that might be helpful?