Eratosthenes

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

// Возвращает массив простых чисел в диапазоне [1..n].
// Последний элемент в массиве - 0.
int* FindPrimes( int n )
{
    assert( n >= 1 );
    bool* numbers = new bool[n + 1]; // 0-ой не используем.
    // Инициализация.
    for( int i = 0; i <= n; ++i ) {
        numbers[i] = true;
    }
    numbers[1] = false;
    // Основной проход.
    for( int i = 2; i < n; ++i ) {
        for( int j = 2; j * i <= n; ++j ) {
            numbers[j * i] = false;
        }
    }
    // Вычислим количество простых.
    int primesCount = 0;
    for( int i = 1; i <= n; ++i ) {
        if( numbers[i] ) {
            ++primesCount;
        }
    }
    // Заполняем массив простых.
    // Выделяем также место и для последнего 0.
    int* primes = new int[primesCount + 1];
    int primesPos = 0;
    for( int i = 1; i <= n; ++i ) {
        if( numbers[i] ) {
            primes[primesPos] = i;
            primesPos++;
        }
    }
    primes[primesCount] = 0;
    delete[] numbers;
    return primes;
}

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

    int* primes = FindPrimes( n );

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

    delete[] primes;
    return 0;
}