feat: add Sieve of Eratosthenes (originally by @thechubbypanda) (TheA…

…lgorithms#2442) * feat: add Sieve of Eratosthenes Originally created by @thechubbypanda. * updating DIRECTORY.md --------- Co-authored-by: github-actions[bot] <github-actions@users.noreply.github.com> Co-authored-by: Keval Kapdee <keval@thechubbypanda.net>
ShuN6211 · Mar 29, 2023 · 1d2c5d9 · 1d2c5d9
1 parent 0f20cdc
commit 1d2c5d9
Show file tree

Hide file tree

Showing 2 changed files with 119 additions and 0 deletions.
diff --git a/DIRECTORY.md b/DIRECTORY.md
@@ -189,6 +189,7 @@
   * [Check Prime](https://github.com/TheAlgorithms/C-Plus-Plus/blob/HEAD/math/check_prime.cpp)
   * [Complex Numbers](https://github.com/TheAlgorithms/C-Plus-Plus/blob/HEAD/math/complex_numbers.cpp)
   * [Double Factorial](https://github.com/TheAlgorithms/C-Plus-Plus/blob/HEAD/math/double_factorial.cpp)
+  * [Eratosthenes](https://github.com/TheAlgorithms/C-Plus-Plus/blob/HEAD/math/eratosthenes.cpp)
   * [Eulers Totient Function](https://github.com/TheAlgorithms/C-Plus-Plus/blob/HEAD/math/eulers_totient_function.cpp)
   * [Extended Euclid Algorithm](https://github.com/TheAlgorithms/C-Plus-Plus/blob/HEAD/math/extended_euclid_algorithm.cpp)
   * [Factorial](https://github.com/TheAlgorithms/C-Plus-Plus/blob/HEAD/math/factorial.cpp)

diff --git a/math/eratosthenes.cpp b/math/eratosthenes.cpp
@@ -0,0 +1,118 @@
+/**
+ * @file
+ * @brief [The Sieve of
+ * Eratosthenes](https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes)
+ * @details
+ * Store an array of booleans where a true value indicates that it's index is
+ * prime. For all the values in the array starting from 2 which we know is
+ * prime, we walk the array in multiples of the current outer value setting them
+ * to not prime. If we remove all multiples of a value as we see it, we'll be
+ * left with just primes.
+ *
+ * Pass "print" as a command line arg to see the generated list of primes
+ * @author [Keval Kapdee](https://github.com/thechubbypanda)
+ */
+
+#include <cassert>   /// For assert
+#include <chrono>    /// For timing the sieve
+#include <iostream>  /// For IO operations
+#include <string>    /// For string handling
+#include <vector>    /// For std::vector
+
+/**
+ * @namespace math
+ * @brief Mathematical algorithms
+ */
+namespace math {
+/**
+ * @brief Performs the sieve
+ * @param vec Array of bools, all initialised to true, where the number of
+ * elements is the highest number we wish to check for primeness
+ * @returns void
+ */
+void sieve(std::vector<bool> *vec) {
+    (*vec)[0] = false;
+    (*vec)[1] = false;
+
+    // The sieve sets values to false as they are found not prime
+    for (uint64_t n = 2; n < vec->size(); n++) {
+        for (uint64_t multiple = n << 1; multiple < vec->size();
+             multiple += n) {
+            (*vec)[multiple] = false;
+        }
+    }
+}
+
+/**
+ * @brief Prints all the indexes of true values in the passed std::vector
+ * @param primes The vector that has been passed through `sieve(...)`
+ * @returns void
+ */
+void print_primes(std::vector<bool> const &primes) {
+    for (uint64_t i = 0; i < primes.size(); i++) {
+        if (primes[i]) {
+            std::cout << i << std::endl;
+        }
+    }
+}
+}  // namespace math
+
+/**
+ * @brief Self-tests the sieve function for major inconsistencies
+ * @returns void
+ */
+static void test() {
+    auto primes = std::vector<bool>(10, true);
+    math::sieve(&primes);
+    assert(primes[0] == false);
+    assert(primes[1] == false);
+    assert(primes[2] == true);
+    assert(primes[3] == true);
+    assert(primes[4] == false);
+    assert(primes[5] == true);
+    assert(primes[6] == false);
+    assert(primes[7] == true);
+    assert(primes[8] == false);
+    assert(primes[9] == false);
+
+    std::cout << "All tests have successfully passed!\n";
+}
+
+/**
+ * @brief Main function
+ * @param argc commandline argument count
+ * @param argv commandline array of arguments
+ * @returns 0 on exit
+ */
+int main(int argc, char *argv[]) {
+    test();  // run self-test implementations
+
+    // The largest prime we will check for
+    auto max = 10000;
+
+    // Store a boolean for every number which states if that index is prime or
+    // not
+    auto primes = std::vector<bool>(max, true);
+
+    // Store the algorithm start time
+    auto start = std::chrono::high_resolution_clock::now();
+
+    // Run the sieve
+    math::sieve(&primes);
+
+    // Time difference calculation
+    auto time = std::chrono::duration_cast<
+                    std::chrono::duration<double, std::ratio<1>>>(
+                    std::chrono::high_resolution_clock::now() - start)
+                    .count();
+
+    // Print the primes if we see that "print" was passed as an arg
+    if (argc > 1 && argv[1] == std::string("print")) {
+        math::print_primes(primes);
+    }
+
+    // Print the time taken we found earlier
+    std::cout << "Time taken: " << time << " seconds" << std::endl;
+
+    return 0;
+}