#include <iostream>

using namespace std;

void writeTask()
{
    cout << "Данная программа находит все натуральные числа, которые можно представить в виде произведения двух простых чисел и которые не превосходят введённое натуральное число N\n";
}

int inputNumber()
{
    const int MIN_NUMBER = 2;
    const int MAX_NUMBER = 2147483647;
    bool isIncorrect;
    int number;
    do
    {
        isIncorrect = false;
        cout << "Введите натурально число N в диапазоне от " << MIN_NUMBER << " до " << MAX_NUMBER << endl;
        cin >> number;
        if (cin.fail())
        {
            cin.clear();
            while (cin.get() != '\n');
            cout << "Введены некорректные данные\n";
            isIncorrect = true;
        }
        if ((!isIncorrect) && (cin.get() != '\n'))
        {
            cin.clear();
            while (cin.get() != '\n');
            cout << "Введены некорректные данные\n";
            isIncorrect = true;
        }
        if ((!isIncorrect) && ((number > MAX_NUMBER) || (number < MIN_NUMBER)))
        {
            cout << "Неправильный диапазон данных\n";
            isIncorrect = true;
        }
    } while (isIncorrect);
    return number;
}

int* ConsistencyUpToNumber(int number)
{
    int* arrayInt = new int[number - 1];
    int i = 0;
    while (i < number - 1)
    {
        arrayInt[i] = i + 2;
        i++;
    }
    return arrayInt;
}

int* arrayOfPrimes(int number)
{
    bool* isPrime = new bool[number];
    for (int i = 2; i * i < number; i++)
    {
        if (isPrime[i])
        {
            for (int j = 2 * i; j < number; j += i)
            {
                isPrime[j] = false;
            }
        }
    }
    int* primeNumbers = new int[number - 1];
    int j = 0;
    for (int i = 2; i < number; i++)
    {
        if (isPrime[i])
        {
            primeNumbers[j] = i;
            j++;
        }
    }
    delete[] isPrime;
    return primeNumbers;
}

int SecondDivision(int arrNumbersElement, int quotient, int number)
{
    int* arrOfPrimes = arrayOfPrimes(number);
    int arrCorrectnessElement = 0;
    int k = 0;
    while ((k < 18) && (arrOfPrimes[k] <= quotient))
    {
        if (quotient == arrOfPrimes[k])
        {
            arrCorrectnessElement = arrNumbersElement;
            k = 18;
        }
        k++;
    }
    delete[] arrOfPrimes;
    return arrCorrectnessElement;
}

int* findingRequiredNumbers(int number)
{
    int* arrOfPrimes = arrayOfPrimes(number);
    int* arrNumbers = ConsistencyUpToNumber(number);
    number--;
    int* arrCorrectness = new int[number];
    for (int i = 0; i < number; i++)
    {
        arrCorrectness[i] = 0;
        int k = 0;
        while ((k < 18) && (arrOfPrimes[k] < arrNumbers[i]))
        {
            if (arrNumbers[i] % arrOfPrimes[k] == 0)
            {
                int quotient = arrNumbers[i] / arrOfPrimes[k];
                arrCorrectness[i] = SecondDivision(arrNumbers[i], quotient, number);
                k = 18;
            }
            k++;
        }
    }
    delete[] arrOfPrimes;
    delete[] arrNumbers;
    return arrCorrectness;
}

void outputNumber(int number, int* arrCorrect)
{
    cout << "Полученные натуральные числа: \n";
    number--;
    int zeroValue = number;
    for (int i = 0; i < number; i++)
    {
        if (arrCorrect[i] != 0)
        {
            cout << arrCorrect[i] << " ";
            zeroValue++;
        }
    }
    if (zeroValue == number)
    {
        cout << "Натуральные числа, соответствующие требованиям, не найдены\n";
    }
}

int main()
{
    setlocale(LC_ALL, "Rus");
    writeTask();
    int n = inputNumber();
    int* arrayOfCorrect = findingRequiredNumbers(n);
    outputNumber(n, arrayOfCorrect);
    delete[] arrayOfCorrect;
    return 0;
}