//  Copyright [2021] <zikai wang>
using namespace std;

void markMultiples(int p, int num[], int user_input_num) {
    // Create a list of consecutive integers from 2 through n: (2, 3, 4, ..., n)
    // Initially, let p equal 2, the smallest prime number.
    int list_2_to_n[1001];
    for (int i = 2; i <= user_input_num + 2; i++) {
        list_2_to_n[i - 2] = i;
    }
    int midle_num = 0;
    for (int i = 0; i <= user_input_num; i++) {
        // Find the first number greater than p in the list that is not marked.
        // If there was no such number, stop.
        // Otherwise, let p now equal this new number(which is the next prime)
        // , and repeat from step 3.
        if (num[i] == 0) {
            p = list_2_to_n[i];
            // Enumerate the multiples of p by counting to n from 2p in
            // increments of p,
            // and mark them in the list (these will be 2p, 3p, 4p, ... 
            // ; the p itself should not be marked).
            for (int curr_num = 2; curr_num * p <= user_input_num; curr_num++) {
                midle_num = curr_num * p;
                num[midle_num] = 1;
            }
        }
    }
}