#include <cstddef>
#include <iostream>

// The Sieve of Eratosthenes
//
//     Pronunciation: air-uh-TOSS-thuh-neez
//
// Suppose you want to find all prime numbers from 2
// up to and including n. Here is one way to do it:
//
//   1. Create a table with all the integers from 0 to n.
//      Immediately cross off 0 and 1: they are not prime.
//
//   2. Now apply the following algorithm:
//
//      a. Go to the next number that is not crossed off.
//         That number must be prime; denote it by p.
//
//      b. Any multiple of p by an integer greater than
//         or equal to 2 cannot be prime, so cross off
//         those multiples.
//
//      c. Go to the next number that is not crossed off
//         and repeat.
//
// Important: Suppose we determine that the next prime
// number is 13. The algorithm above appears to tell us
// to start crossing off
//
//      26, 39, 52, 65, 78, 91, 104, 117,
//      130, 143, 156, 169, 182, ...
//
// However, consider the first twelve of these:
//
//      26           =  2 x 13
//      39           =  3 x 13
//      52 =  4 x 13 =  2 x 26
//      65           =  5 x 13
//      78 =  6 x 13 =  2 x 39
//      91           =  7 x 13
//     104 =  8 x 13 =  2 x 52
//     117 =  9 x 13 =  3 x 39
//     130 = 10 x 13 =  2 x 65
//     143           = 11 x 13
//     156 = 12 x 13 =  2 x 78
//     169 = 13 x 13
//
// Every multiple of 13 less than 13 x 13 must also
// have a prime factor smaller than 13. Consequently,
// all these values have already been crossed off.
//
// Thus, once we determine that 13 is prime, we only
// need to start with
//
//      13 x 13, 14 x 13, 15 x 13, 16 x 13, ...
//
// We can improve this slightly more. Since 13 > 2,
// we do not need to multiply 13 by any even number.
// Those products are even and have already been
// crossed off.
//
// Thus, we only need to consider
//
//      13 x 13, 15 x 13, 17 x 13, 19 x 13, ...
//
// More generally, after dealing with the prime 2,
// we only need to consider odd prime numbers and odd
// multiples of those prime numbers.
//
// For your information, you should find this many
// prime numbers up to and including a given n:
//
//       n       Number of       Largest prime
//                 primes       no greater than n
//
//      100          25              97
//      200          46             199
//      300          62             293
//      400          78             397
//      500          95             499
//      600         109             599
//      700         125             691
//      800         139             797
//      900         154             887
//     1000         168             997
//     1100         184            1097
//     1200         196            1193
//     1300         211            1297
//     1400         222            1399
//     1500         239            1499
//     1600         251            1597
//     1700         266            1699
//     1800         278            1789
//     1900         290            1889
//     2000         303            1999

// Function declarations
void find_primes(
    bool              table[],
    std::size_t const capacity
);

void print_primes(
    bool        const table[],
    std::size_t const capacity
);

int main();

// Function definitions
int main() {
    std::size_t const MAXIMUM{ 2000 };
    bool table[MAXIMUM + 1];

    std::size_t n{};

    std::cout << "Enter a positive integer no greater than "
              << MAXIMUM << ": ";
    std::cin  >> n;

    if ( n > MAXIMUM ) {
        std::cout << "The integer is too large." << std::endl;
        return 1;
    }

    find_primes( table, n + 1 );
    print_primes( table, n + 1 );

    return 0;
}

// Set table[k] to true exactly when k is prime.

void find_primes(
    bool              table[],
    std::size_t const capacity
) {
    // Enter your implementation here.
}

// Print all the prime numbers represented by the table
// and then print the number of primes found.

void print_primes(
    bool        const table[],
    std::size_t const capacity
) {
    std::size_t count{ 0 };

    // Enter your implementation here.

    std::cout << std::endl;
    std::cout << "There were " << count
              << " prime numbers listed." << std::endl;
}




























// Do have fun with this one.
//
// Eratosthenes lived approximately from 276 BCE to
// 194 BCE, so surely you can figure this out. :-)






























































// Here is one solution:

/*
void find_primes(
    bool              table[],
    std::size_t const capacity
) {
    // Initially assume every entry is prime.
    for ( std::size_t k{ 0 }; k < capacity; ++k ) {
        table[k] = true;
    }

    // 0 and 1 are not prime.
    if ( capacity > 0 ) {
        table[0] = false;
    }

    if ( capacity > 1 ) {
        table[1] = false;
    }

    // Cross off all even numbers greater than 2.
    for ( std::size_t k{ 4 }; k < capacity; k += 2 ) {
        table[k] = false;
    }

    // We now only have to consider odd candidates.
    for ( std::size_t p{ 3 }; p < capacity/p; p += 2 ) {
        if ( table[p] ) {
            // Everything less than p*p that is a
            // multiple of p has already been crossed off.
            //
            // Since p is odd, adding 2*p moves directly
            // to the next odd multiple of p.
            for ( std::size_t multiple{ p*p };
                  multiple < capacity;
                  multiple += 2*p ) {
                table[multiple] = false;
            }
        }
    }
}

void print_primes(
    bool        const table[],
    std::size_t const capacity
) {
    std::size_t count{ 0 };
    bool first{ true };

    for ( std::size_t k{ 2 }; k < capacity; ++k ) {
        if ( table[k] ) {
            if ( !first ) {
                std::cout << ", ";
            }

            std::cout << k;
            first = false;
            ++count;
        }
    }

    std::cout << std::endl;
    std::cout << "There were " << count
              << " prime numbers listed." << std::endl;
}
*/