#include <stdio.h>

int main() {
    int n, p, i;

    printf(
        "Calculating all primes <= n,\n"
        "using the sieve of Eratosthenes\n"
    );
    printf("Input n:\n");
    scanf("%d", &n);
    bool* a = new bool[n+1];
    for (i = 0; i <= n; ++i)
        a[i] = true;

    a[0] = false;       // 0 and 1 are not primes
    a[1] = false;
    a[2] = true;        // 2 is the first prime

    p = 2;
    while (p <= n/p) {  // Equivalently: p*p <= n
        // Cross out the multiples of p
        i = p*p;
        while (i <= n) {
            a[i] = false;
            i += p;
        }
        // Find the next prime, i.e.
        // the first non-crossed element
        ++p;
        while (p <= n && !a[p])
            ++p;
    }

    // Print the results
    int numPrimes = 0;
    for (i = 0; i <= n; ++i) {
        if (a[i]) {     // i is a prime number
            // Separate numbers by a space, or start new lines
            // after each 10 numbers
            if (numPrimes > 0) {
                if (numPrimes % 10 == 0) {
                    printf("\n"); // New line after 10 numbers,
                } else {
                    printf(" ");  // otherwise, a space
                }
            }
            printf("%d", i);
            ++numPrimes;
        }
    }
    printf("\n");
    delete[] a;
    return 0;
}