1//! @file prime.cpp
2//! @author ryftchen
3//! @brief The definitions (prime) in the numeric module.
4//! @version 0.1.0
5//! @copyright Copyright (c) 2022-2025 ryftchen. All rights reserved.
6
7#include "prime.hpp"
8
9namespace numeric::prime
10{
11//! @brief Function version number.
12//! @return version number (major.minor.patch)
13const char* version() noexcept
14{
15 static const char* const ver = "0.1.0";
16 return ver;
17}
18
19std::vector<std::uint32_t> Prime::eratosthenes(const std::uint32_t limit)
20{
21 std::vector<std::uint32_t> storage{};
22 std::vector<bool> isPrime(limit + 1, true);
23
24 isPrime[0] = false;
25 isPrime[1] = false;
26 for (std::uint32_t i = 2; i <= limit; ++i)
27 {
28 if (isPrime[i])
29 {
30 for (std::uint32_t j = (i * i); j <= limit; j += i)
31 {
32 isPrime[j] = false;
33 }
34 storage.emplace_back(args&: i);
35 }
36 }
37 return storage;
38}
39
40std::vector<std::uint32_t> Prime::euler(const std::uint32_t limit)
41{
42 std::vector<std::uint32_t> storage{};
43 std::vector<bool> isPrime(limit + 1, true);
44
45 isPrime[0] = false;
46 isPrime[1] = false;
47 for (std::uint32_t i = 2; i <= limit; ++i)
48 {
49 if (isPrime[i])
50 {
51 storage.emplace_back(args&: i);
52 }
53
54 for (std::uint32_t j = 1; (j <= storage.size()) && ((i * storage[j - 1]) <= limit); ++j)
55 {
56 const std::uint32_t composite = i * storage[j - 1];
57 isPrime[composite] = false;
58 if ((i % storage[j - 1]) == 0)
59 {
60 break;
61 }
62 }
63 }
64 return storage;
65}
66} // namespace numeric::prime
67