Sieve

// Выводит все простые числа в диапазоне [1, n].

#include <assert.h>
#include <iostream>
using std::cin;
using std::cout;

// Обертка массива целых чисел.
struct CSimpleIntArray {
    int* Data = 0;
    int Size = 0;

    CSimpleIntArray() = default;
    explicit CSimpleIntArray( int size ) : Data( new int[size] ), Size( size ) {}
    CSimpleIntArray( const CSimpleIntArray& other ) = delete;
    CSimpleIntArray( CSimpleIntArray&& other );
    ~CSimpleIntArray() { delete[] Data; }
};

inline CSimpleIntArray::CSimpleIntArray( CSimpleIntArray&& other ) :
    Data( other.Data ),
    Size( other.Size )
{
    other.Data = 0;
    other.Size = 0;
}

// ------------------------------------------------------------------------------------------------

CSimpleIntArray GetPrimes( int n )
{
    assert( n >= 1 );
    int primesCount = 0;

    // Выделяем массив под решето Эратосфена.
    bool* sieve = new bool[n + 1];
    sieve[0] = false;
    sieve[1] = false;
    for( int i = 2; i <= n; ++i ) {
        sieve[i] = true;
    }

    // Выкалываем составные числа.
    int currentPrime = 2;
    while( currentPrime <= n ) {
        ++primesCount;
        // Выкалываем числа, кратные currentPrime.
        for( int k = 2; k * currentPrime <= n; ++k ) {
            sieve[k * currentPrime] = false;
        }
        // Двигаем currentPrime на следующее простое число.
        for( ++currentPrime; currentPrime <= n && sieve[currentPrime] == false; ++currentPrime ) {}
    }

    // Создадим и запомним массив чисел.
    CSimpleIntArray primes( primesCount );

    int currentIndex = 0;
    for( int i = 0; i <= n; ++i ) {
        if( sieve[i] == true ) {
            assert( currentIndex < primesCount );
            primes.Data[currentIndex++] = i;
        }
    }

    delete[] sieve;
    return primes;
}

int main()
{
    int n = 0;
    cin >> n;

    CSimpleIntArray primes = GetPrimes( n );

    for( int i = 0; i < primes.Size; ++i ) {
        cout << primes.Data[i] << " ";
    }

    return 0;
}