3
\$\begingroup\$

I wrote a simple prime number generator in C++17. The function generate_primes(max) generates all prime numbers up to max. I aimed for maximum portability. Here's the code:

#include <cstdint>
#include <iostream>
#include <set>
#include <range/v3/view/iota.hpp>

namespace view = ranges::view;

using number_t = std::uint_fast32_t;
using numbers_t = std::set<number_t>;

numbers_t generate_primes(number_t max)
{
    if (max < 2)
        return {};

    numbers_t primes{view::ints(number_t(2), max)};
    for (number_t n = 2; n * n <= max; ++n) {
        if (primes.find(n) != primes.end()) {
            for (number_t m = 2; m <= max / n; ++m)
                primes.erase(n * m);
        }
    }
    return primes;
}

I used the ints utility from the Ranges library to populate primes. view::ints(number_t(2), max) lazily generates all the integers of type number_t that is greater or equal to 2 and that is less than or equal to max in ascending order. In C++20, the Ranges library is standardized.

Example usage:

void print(std::ostream& os, const numbers_t& nums)
{
    // convert to unsigned long so that it can be portability printed
    for (unsigned long n : nums)
        os << n << "\n";
}

int main()
{
    print(std::cout, generate_primes(100));
}

Output:

2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97
\$\endgroup\$
  • \$\begingroup\$ @TobySpeight I only used view::ints a single time, does it deserve so much promotion? :D \$\endgroup\$ – L. F. Jul 12 at 11:39
  • 1
    \$\begingroup\$ Not really - I was just trying to find something different to give the question a unique title. I don't mind if you change it again. (I don't think the "unique title" rule works very well here on CR, unlike the other stacks...) \$\endgroup\$ – Toby Speight Jul 12 at 12:01
1
\$\begingroup\$

It may well be more efficient to compute std::sqrt(max) once upfront than to multiply n * n every time around the loop.

Removing an element by value from the set is O(log n), where n is the set size at the time. This will likely make this method slower than writing to elements in a fixed-size storage (such as a std::vector that's never resized), and creating the return set from that. Also, find() is much slower than vector lookup.

I think we can probably test m * n <= max instead of the more expensive m <= max / n, if we can arrange that the multiplication doesn't overflow. It will be fine if 2 * n < std::numeric_limits<number_t>::max() - max. Also, no need to start at 2 * n when removing - we can start at n * n instead, as all the lower multiples have already been removed due to their smaller factor(s).

And a tiny improvement to the test code - we can stream a single character '\n' to output rather than the string "\n".

\$\endgroup\$
  • \$\begingroup\$ How to make sure that std::sqrt(max) is decently accurate? I don't think a uint_fast32_t can be losslessly converted to double ... \$\endgroup\$ – L. F. Jul 12 at 11:28
  • \$\begingroup\$ That's a good question - you're right that there's only a lower bound on the size of std::uint_fast32_t and no upper bound. My instinct would be to simply round up the result using std::ceil, but you if you're sufficiently paranoid, you could always advance to the next representable value after that. Or, fall back to the n * n test using ||, so the expensive version would only be evaluated the last time around the loop (or last two times if there's a rounding problem). (cont...) \$\endgroup\$ – Toby Speight Jul 12 at 12:07
  • \$\begingroup\$ ... IOW, auto const limit = static_cast<std::uint_fast32_t>(std::ceil(std::sqrt(max))); for (...; n <= limit || n * n <= max; ...) \$\endgroup\$ – Toby Speight Jul 12 at 12:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.