Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c++ > #91476

Re: Sieve of Eratosthenes

From Ben Bacarisse <ben.usenet@bsb.me.uk>
Newsgroups comp.lang.c++
Subject Re: Sieve of Eratosthenes
Date 2023-08-31 03:18 +0100
Organization A noiseless patient Spider
Message-ID <87wmxckl8x.fsf@bsb.me.uk> (permalink)
References (4 earlier) <56146f63-17d7-40cc-8c42-4f29c922a8c4n@googlegroups.com> <874jkknizq.fsf@bsb.me.uk> <861qfmyft6.fsf@linuxsc.com> <873502n61v.fsf@bsb.me.uk> <86v8cwt4yd.fsf@linuxsc.com>

Show all headers | View raw

Tim Rentsch <tr.17687@z991.linuxsc.com> writes:

> Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
>
>> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>>
>>> Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
>>>
>>>> I wanted to try a newer algorithm, so I coded up a rather naive
>>>> version of Atkin & Bernstein's sieve in C.  It needs some tidying
>>>> and I imagine a bit can be shaved off the time.
>>>
>>> Thank you for this.  Would you mind posting your code?
>>
>> Hmm...  It's a bit of a mess... but sure.  [...]
>
> It looks quite okay.  I haven't yet had time to look at it
> closely but I look forward to doing so.

About 20% of the time was spent counting the primes, so I added a
population count function to the bitset operations.  And there's an
obvious halving one can do on the upper bound of the first loop.  That
brought the time down to about 28 seconds.

>>> Also do
>>> you have a reference for the Atkin/Bernstein algorithm (or even
>>> better, code?)?
>>
>> Well, there's this:  https://en.wikipedia.org/wiki/Sieve_of_Atkin
>
> Excellent!  And this page has a link to DJ Bernstein's fast
> primes code, which is stunningly swift.

I haven't looked at it yet.  It would probably have put me off!

> Thank you for both.

You're welcome.

-- 
Ben.

Back to comp.lang.c++ | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-16 15:37 +0200
  Re: Sieve of Eratosthenes wij <wyniijj5@gmail.com> - 2023-08-16 10:57 -0700
    Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-16 20:21 +0200
      Re: Sieve of Eratosthenes wij <wyniijj5@gmail.com> - 2023-08-16 12:17 -0700
    Re: Sieve of Eratosthenes Paavo Helde <eesnimi@osa.pri.ee> - 2023-08-16 21:44 +0300
      Re: Sieve of Eratosthenes wij <wyniijj5@gmail.com> - 2023-08-16 12:09 -0700
  Re: Sieve of Eratosthenes "Alf P. Steinbach" <alf.p.steinbach@gmail.com> - 2023-08-16 23:17 +0200
    Re: Sieve of Eratosthenes "Alf P. Steinbach" <alf.p.steinbach@gmail.com> - 2023-08-16 23:21 +0200
    Re: Sieve of Eratosthenes "Alf P. Steinbach" <alf.p.steinbach@gmail.com> - 2023-08-16 23:39 +0200
      Re: Sieve of Eratosthenes "Alf P. Steinbach" <alf.p.steinbach@gmail.com> - 2023-08-16 23:59 +0200
        Re: Sieve of Eratosthenes "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2023-08-16 16:27 -0700
    Re: Sieve of Eratosthenes red floyd <no.spam.here@its.invalid> - 2023-08-16 18:06 -0700
      Re: Sieve of Eratosthenes Tim Rentsch <tr.17687@z991.linuxsc.com> - 2023-08-16 19:26 -0700
        Re: Sieve of Eratosthenes Öö Tiib <ootiib@hot.ee> - 2023-08-27 12:26 -0700
          Re: Sieve of Eratosthenes Ben Bacarisse <ben.usenet@bsb.me.uk> - 2023-08-28 00:49 +0100
            Re: Sieve of Eratosthenes Öö Tiib <ootiib@hot.ee> - 2023-08-27 23:23 -0700
              Re: Sieve of Eratosthenes "Alf P. Steinbach" <alf.p.steinbach@gmail.com> - 2023-08-28 15:53 +0200
                Re: Sieve of Eratosthenes Öö Tiib <ootiib@hot.ee> - 2023-08-28 09:03 -0700
                Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-28 18:47 +0200
                Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-30 13:01 +0200
                Re: Sieve of Eratosthenes Muttley@dastardlyhq.com - 2023-08-30 15:38 +0000
                Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-30 18:31 +0200
                Re: Sieve of Eratosthenes Muttley@dastardlyhq.com - 2023-08-31 08:22 +0000
                Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-31 11:00 +0200
                Re: Sieve of Eratosthenes Muttley@dastardlyhq.com - 2023-08-31 15:23 +0000
                Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-31 17:28 +0200
                Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-31 11:52 +0200
                Re: Sieve of Eratosthenes Muttley@dastardlyhq.com - 2023-08-31 15:22 +0000
                Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-31 17:32 +0200
                Re: Sieve of Eratosthenes Muttley@dastardlyhq.com - 2023-08-31 15:44 +0000
                Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-31 17:50 +0200
                Re: Sieve of Eratosthenes Muttley@dastardlyhq.com - 2023-09-01 10:26 +0000
                Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-09-01 12:59 +0200
                Re: Sieve of Eratosthenes Muttley@dastardlyhq.com - 2023-09-01 12:30 +0000
                Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-09-01 15:33 +0200
                Re: Sieve of Eratosthenes Muttley@dastardlyhq.com - 2023-09-01 13:49 +0000
                Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-09-01 15:59 +0200
                Re: Sieve of Eratosthenes Muttley@dastardlyhq.com - 2023-09-01 14:03 +0000
                Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-09-01 16:15 +0200
                Re: Sieve of Eratosthenes Muttley@dastardlyhq.com - 2023-09-01 14:39 +0000
                Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-09-01 16:59 +0200
                Re: Sieve of Eratosthenes Muttley@dastardlyhq.com - 2023-09-01 15:01 +0000
                Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-09-01 17:05 +0200
                Re: Sieve of Eratosthenes Muttley@dastardlyhq.com - 2023-09-01 15:08 +0000
                Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-09-01 17:15 +0200
                Re: Sieve of Eratosthenes Ben Bacarisse <ben.usenet@bsb.me.uk> - 2023-08-31 21:33 +0100
                Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-09-01 05:35 +0200
                Re: Sieve of Eratosthenes scott@slp53.sl.home (Scott Lurndal) - 2023-08-31 14:43 +0000
                Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-31 16:57 +0200
                Re: Sieve of Eratosthenes scott@slp53.sl.home (Scott Lurndal) - 2023-08-31 16:10 +0000
                Re: Sieve of Eratosthenes Muttley@dastardlyhq.com - 2023-08-31 15:25 +0000
                Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-31 17:33 +0200
                Re: Sieve of Eratosthenes scott@slp53.sl.home (Scott Lurndal) - 2023-08-31 16:12 +0000
                Re: Sieve of Eratosthenes Ben Bacarisse <ben.usenet@bsb.me.uk> - 2023-08-28 23:08 +0100
            Re: Sieve of Eratosthenes Tim Rentsch <tr.17687@z991.linuxsc.com> - 2023-08-28 15:15 -0700
              Re: Sieve of Eratosthenes Ben Bacarisse <ben.usenet@bsb.me.uk> - 2023-08-28 23:41 +0100
                Re: Sieve of Eratosthenes Tim Rentsch <tr.17687@z991.linuxsc.com> - 2023-08-30 17:45 -0700
                Re: Sieve of Eratosthenes Ben Bacarisse <ben.usenet@bsb.me.uk> - 2023-08-31 03:18 +0100
          Re: Sieve of Eratosthenes Tim Rentsch <tr.17687@z991.linuxsc.com> - 2023-08-28 15:08 -0700
      Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-17 08:42 +0200
        Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-17 11:38 +0200
          Re: Sieve of Eratosthenes "Alf P. Steinbach" <alf.p.steinbach@gmail.com> - 2023-08-17 12:50 +0200
            Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-17 13:10 +0200
            Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-17 17:47 +0200
            Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-21 11:00 +0200
              Re: Sieve of Eratosthenes Muttley@dastardlyhq.com - 2023-08-21 17:19 +0000
                Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-21 19:50 +0200
                Re: Sieve of Eratosthenes Muttley@dastardlyhq.com - 2023-08-21 18:12 +0000
                Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-21 20:22 +0200
                Re: Sieve of Eratosthenes Muttley@dastardlyhq.com - 2023-08-21 19:01 +0000
                Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-22 05:27 +0200
                Re: Sieve of Eratosthenes Öö Tiib <ootiib@hot.ee> - 2023-08-21 23:25 -0700
                Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-22 11:23 +0200
                Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-22 11:59 +0200
                Re: Sieve of Eratosthenes Öö Tiib <ootiib@hot.ee> - 2023-08-22 05:15 -0700
                Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-22 14:23 +0200
                Re: Sieve of Eratosthenes Muttley@dastardlyhq.com - 2023-08-22 06:56 +0000
                Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-22 11:27 +0200
                Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-22 11:34 +0200
                Re: Sieve of Eratosthenes Muttley@dastardlyhq.com - 2023-08-22 14:13 +0000
                Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-22 16:17 +0200
                Re: Sieve of Eratosthenes Muttley@dastardlyhq.com - 2023-08-22 14:27 +0000
                Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-22 16:48 +0200
                Re: Sieve of Eratosthenes Muttley@dastardlyhq.com - 2023-08-22 14:57 +0000
                Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-22 17:00 +0200
                Re: Sieve of Eratosthenes Muttley@dastardlyhq.com - 2023-08-22 17:56 +0000
                Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-22 20:13 +0200
                Re: Sieve of Eratosthenes Muttley@dastardlyhq.com - 2023-08-22 18:18 +0000
                Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-22 20:50 +0200
                Re: Sieve of Eratosthenes Muttley@dastardlyhq.com - 2023-08-23 06:51 +0000
                Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-23 09:59 +0200
                Re: Sieve of Eratosthenes Richard Damon <Richard@Damon-Family.org> - 2023-08-23 07:52 -0400
                Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-23 14:40 +0200
                Re: Sieve of Eratosthenes Muttley@dastardlyhq.com - 2023-08-23 14:24 +0000
                Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-23 16:30 +0200
                Re: Sieve of Eratosthenes Muttley@dastardlyhq.com - 2023-08-23 14:36 +0000
                Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-23 16:38 +0200
                Re: Sieve of Eratosthenes Muttley@dastardlyhq.com - 2023-08-23 14:43 +0000
                Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-23 16:45 +0200
                Re: Sieve of Eratosthenes Muttley@dastardlyhq.com - 2023-08-23 17:49 +0000
                Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-23 20:05 +0200
                Re: Sieve of Eratosthenes Muttley@dastardlyhq.com - 2023-08-24 17:18 +0000
                Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-24 19:20 +0200
                Re: Sieve of Eratosthenes Daniel <danielaparker@gmail.com> - 2023-08-23 11:13 -0700
                Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-23 20:17 +0200
                Re: Sieve of Eratosthenes "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2023-08-23 11:20 -0700
                Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-23 20:24 +0200
                Re: Sieve of Eratosthenes Muttley@dastardlyhq.com - 2023-08-24 17:25 +0000
                Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-24 19:29 +0200
                Re: Sieve of Eratosthenes Muttley@dastardlyhq.com - 2023-08-24 17:40 +0000
                Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-24 19:49 +0200
                Re: Sieve of Eratosthenes Muttley@dastardlyhq.com - 2023-08-25 16:07 +0000
                Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-25 18:10 +0200
                Re: Sieve of Eratosthenes Muttley@dastardlyhq.com - 2023-08-25 16:15 +0000
                Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-25 18:18 +0200
                Re: Sieve of Eratosthenes Muttley@dastardlyhq.com - 2023-08-26 08:03 +0000
                Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-26 10:16 +0200
                Re: Sieve of Eratosthenes Muttley@dastardlyhq.com - 2023-08-26 08:27 +0000
                Re: Sieve of Eratosthenes Daniel <danielaparker@gmail.com> - 2023-08-23 11:37 -0700
                Re: Sieve of Eratosthenes "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2023-08-26 15:33 -0700
                Re: Sieve of Eratosthenes Muttley@dastardlyhq.com - 2023-08-23 14:20 +0000
                Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-23 16:32 +0200
                Re: Sieve of Eratosthenes Muttley@dastardlyhq.com - 2023-08-23 14:41 +0000
                Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-23 16:47 +0200
                Re: Sieve of Eratosthenes Muttley@dastardlyhq.com - 2023-08-23 17:51 +0000
                Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-23 20:09 +0200
                Re: Sieve of Eratosthenes scott@slp53.sl.home (Scott Lurndal) - 2023-08-23 18:51 +0000
                Re: Sieve of Eratosthenes "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2023-08-24 11:25 -0700
                Re: Sieve of Eratosthenes Muttley@dastardlyhq.com - 2023-08-24 17:22 +0000
                Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-24 19:27 +0200
                Re: Sieve of Eratosthenes Muttley@dastardlyhq.com - 2023-08-24 17:37 +0000
                Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-24 19:52 +0200
                Re: Sieve of Eratosthenes Muttley@dastardlyhq.com - 2023-08-25 16:07 +0000
                Re: Sieve of Eratosthenes Daniel <danielaparker@gmail.com> - 2023-08-23 08:00 -0700
                Re: Sieve of Eratosthenes scott@slp53.sl.home (Scott Lurndal) - 2023-08-22 15:49 +0000
                Re: Sieve of Eratosthenes Muttley@dastardlyhq.com - 2023-08-22 17:58 +0000
                Re: Sieve of Eratosthenes scott@slp53.sl.home (Scott Lurndal) - 2023-08-22 18:24 +0000
                Re: Sieve of Eratosthenes Muttley@dastardlyhq.com - 2023-08-23 06:50 +0000
    Re: Sieve of Eratosthenes wij <wyniijj5@gmail.com> - 2023-08-17 13:43 -0700
      Re: Sieve of Eratosthenes "Alf P. Steinbach" <alf.p.steinbach@gmail.com> - 2023-08-18 02:00 +0200
        Re: Sieve of Eratosthenes wij <wyniijj5@gmail.com> - 2023-08-18 05:01 -0700
          Re: Sieve of Eratosthenes wij <wyniijj5@gmail.com> - 2023-08-18 17:02 -0700
  Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-28 06:15 +0200
  Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-28 09:43 +0200
  Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-29 20:34 +0200
    Re: Sieve of Eratosthenes Bonita Montero <Bonita.Montero@gmail.com> - 2023-08-30 19:02 +0200

csiph-web