'Can this recursive template function ever compile?
I have this code that should implement the Sieve of Eratosthenes. Start with all number >= 2. Get the first number (2), print it and remove all multiples of it. Get the second number (3), print it and remove all multiples of it. And so on.
#include <iostream>
#include <ranges>
template<int limit>
void next(auto sieve) {
int prime = sieve.front();
if (prime < limit) {
std::cout << " " << prime;
next<limit>(sieve | std::views::filter([prime](const auto& value) { return value % prime != 0; }));
}
}
int main() {
std::cout << "Primes:";
next<100>(std::views::iota(2));
std::cout << std::endl;
}
The recursion is limited to show only primes smaller than 100. Or is it?
I think this code is perfectly valid but will never finish compiling.
The reason for this being the auto sieve argument in next and if (prime < limit) not being a constexpr. In each instance of next the compiler has to validate the recursive call to next and deduce the template arguments and the recursion never ends.
Am I right or just impatient? It's compiling for over 2 hours now, eating up 4GB of memory so far.
If so is there a way to make the recursion terminate? Some form of type erasure? The end goal would be to build an infinite range/view of all prime numbers.
Update: The use of an infinite range is intentional, do not suggest solutions without it. The end goal is an infinite range of prime numbers lazily evaluated as you iterate over the range.
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|
