# Prime number sieve using ranges::view::ints

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

• @TobySpeight I only used view::ints a single time, does it deserve so much promotion? :D – L. F. Jul 12 at 11:39
• 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...) – Toby Speight Jul 12 at 12:01

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".
• 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 ... – L. F. Jul 12 at 11:28
• 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...) – Toby Speight Jul 12 at 12:07
• ... IOW, auto const limit = static_cast<std::uint_fast32_t>(std::ceil(std::sqrt(max))); for (...; n <= limit || n * n <= max; ...) – Toby Speight Jul 12 at 12:08