#include <stdio.h>
#include <stdlib.h>

void prime(int N)
{
    unsigned char * sieve = malloc(N+1);
    for(int i = 0; i <= N; ++i) sieve[i] = 1-i%2;
    sieve[0] = sieve[1] = 1; sieve[2] = 0;
    for (int i = 3; i * i <= N; i += 2)
        for(int k = 2*i; k <= N; k += i) sieve[k] = 1;

    printf("Prime numbers:\n");
    for (int i = 2; i <= N; ++i)
        if (sieve[i] == 0)
            printf("%d\n", i);
    free(sieve);

}

int main() {
    int N;
    scanf("%d", &N);
    prime(N);
}