Sieve of Eratosthenes. Not sure how to implement it exactly

Question

Here's my code:

#include <vector>
#include <cmath>
#include <string>
#include <iostream>
#include <algorithm>

using namespace std;

   
bool is_prime(int num) {
  for (int j = 2; j <= sqrt(num); j++) {

    if (num % j == 0) {
      return false;
    }

  }
  return true;
}

int main() {
  int n = 100;
  int p = 2;

  vector < int > multiples;
  vector < int > integers;
  vector < int > primes;
  for (int i = 2; i <= n; i++) {
    integers.push_back(i);
  }
  for (int i = p; i <= n / p; i += p) {
    multiples.push_back(i);
  }

}

Here is the Wikipedia description of the Sieve.

But now I'm on step 4 and don't really know how to do this, also not sure how to put all this in a while loop so it does it enough times.

Answer 1

I would not recommend blindly following instructions. As you can see, you have trouble translating them into code, so just don't. Try to understand the algorithm first, then iterate through it on paper and only then write it in code. It should be easier to do based on the iteration you have done.

Since you can find the implementation anywhere, it won't be much of a spoiler if I provide it to you.

The goal is to find all prime numbers, the crucial thing is to realize that all non-prime numbers (non-prime) multiples of some prime number. That follow from its unique factorization. If you reverse it, for each prime n, none of 2*n,3*n,4*n... are primes. So if you start from n=2, you can rule out all those non-primes. You can then do n=3,n=5... for all primes and will be left with only prime numbers. Well that's it.

So about the implementation:

1. We need to have a table of numbers for marking, at the end only unmarked(false) numbers are the found primes. Also make a type for the returned primes.

   using table_t = std::vector<bool>;
   using primes_t = std::vector<std::size_t>;
   

2. Let's say we want to find all primes between 1 and n, this is how the function might look like:

   primes_t sieve(std::size_t n){
       //...
   }
   

3. It will be handy to have a separate function for obtaining the primes from the table:

   std::vector<std::size_t> get_primes(const table_t& table){
       std::vector<std::size_t> res;
   
       for(std::size_t i=0;i<table.size();++i)
           if(!table[i])// All unmarked numbers are primes
               res.push_back(i);
       return res;
   }
   

4. Now, let's implement the smallest unit of work: marking all multiples of a given number.

   // mark [2*k,3*k...] in table
   void mark_multiples(table_t& table, std::size_t k){
       std::size_t m=2*k;
       while(m<N){
           table[m]=false;
           m+=k;
       }
   }
   

5. Another piece of the puzzle is finding the smallest unmarked element in the table from a given offset

   std::size_t find_next_smallest_unmarked(const table_t& table,std::size_t start){
       auto it = std::find(table.cbegin()+start,table.cend(),false);
       return std::distance(table.cbegin(),it);
   }
   

6. Now we need to repeat all of the above in a, thus the full sieve looks like:

   primes_t sieve(std::size_t n){
       auto table = table_t(N, false);
   
       std::size_t p =2 ;
       while(p<N){
           mark_multiples(table,p);
           p = find_next_smallest_unmarked(table, p+1);
       }
       return get_primes(table);
   }
   

Note that the function can almost be read like the instructions from Wikipedia. I find this bottom-to-top approach easier than trying to write it all in one big function.

The main:

int main(){
    auto primes = sieve(100);

    std::copy(primes.cbegin(),primes.cend(),std::ostream_iterator<std::size_t>(std::cout,", "));
}

Output:

0, 1, 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,

I am sure that my implementation might raise some more questions for you, especially the iterators. That's good, run it through a debugger to see what each function accepts, does, and returns. Go to cppreference and see what each std:: symbol means.