mirror of
https://gitlab.com/mfocko/CodeWars.git
synced 2024-10-18 02:42:07 +02:00
63 lines
1.4 KiB
C++
63 lines
1.4 KiB
C++
#include <cassert>
|
|
#include <vector>
|
|
|
|
namespace {
|
|
|
|
inline std::size_t index(unsigned p) { return p - 2; }
|
|
inline bool is_prime(const std::vector<bool> &primes, unsigned p) {
|
|
return primes[index(p)];
|
|
}
|
|
|
|
void discard_multiples(std::vector<bool> &primes, unsigned p) {
|
|
for (auto k = 2; index(p * k) < primes.size(); k++) {
|
|
primes[index(p * k)] = false;
|
|
}
|
|
}
|
|
|
|
void discard_even(std::vector<bool> &primes) { discard_multiples(primes, 2); }
|
|
|
|
std::vector<unsigned> construct_primes(const std::vector<bool> &primes) {
|
|
std::vector<unsigned> result;
|
|
|
|
for (auto p = 0u; p < primes.size(); p++) {
|
|
if (primes[p]) {
|
|
result.push_back(p + 2);
|
|
}
|
|
}
|
|
|
|
return result;
|
|
}
|
|
|
|
} // namespace
|
|
|
|
// Generate an array containing every prime number between 0 and the num
|
|
// specified (inclusive)
|
|
std::vector<unsigned> prime(unsigned n) {
|
|
if (n < 2) {
|
|
return {};
|
|
}
|
|
|
|
std::vector<bool> primes(n - 1, true);
|
|
discard_even(primes);
|
|
|
|
for (auto p = 3u; p <= n; p += 2) {
|
|
if (!is_prime(primes, p)) {
|
|
continue;
|
|
}
|
|
|
|
discard_multiples(primes, p);
|
|
}
|
|
|
|
return construct_primes(primes);
|
|
}
|
|
|
|
int main() {
|
|
assert(prime(0) == std::vector<unsigned>{});
|
|
assert(prime(1) == std::vector<unsigned>{});
|
|
assert(prime(2) == std::vector<unsigned>{2});
|
|
assert((prime(23) == std::vector<unsigned>{2, 3, 5, 7, 11, 13, 17, 19, 23}));
|
|
assert(
|
|
(prime(30) == std::vector<unsigned>{2, 3, 5, 7, 11, 13, 17, 19, 23, 29}));
|
|
|
|
return 0;
|
|
}
|