#include <iostream>

using namespace std;

short inputNumber()
{
    const short MIN_NUMBER = 4;
    const short MAX_NUMBER = 127;
    bool isIncorrect;
    short number;
    do
    {
        isIncorrect = false;
        cout << "Введите натурально число N\n";
        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;
}

short* arrayOfInteger(short number)
{
    short* arrayInt = new short[number];
    for (int i = 0; i < number; i++)
    {
        arrayInt[i] = i + 2;
    }
    return arrayInt;
}

short* findingRequiredNumbers(short number)
{
    const short arrOfPrimes[18] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61};
    short* arrNumbers = arrayOfInteger(number);
    number--;
    short* arrCorrectness = new short[number];
    for (int i = 0; i < number; i++)
    {
        int k = 0;
        while ((k < 18) && (arrOfPrimes[k] < arrNumbers[i]))
        {
            if (arrNumbers[i] % arrOfPrimes[k] == 0)
            {
                short quotient = arrNumbers[i] / arrOfPrimes[k];
                k = 0;
                while ((k < 18) && (arrOfPrimes[k] <= quotient))
                {
                    if (quotient == arrOfPrimes[k])
                    {
                        arrCorrectness[i] = 1;
                        k = 18;
                    }
                    else
                    {
                        arrCorrectness[i] = 0;
                        k++;
                    }
                }
            }else
            {
                k++;
            }
        }

    }
    return arrCorrectness;
}

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

int main()
{
    setlocale(LC_ALL, "Rus");
    cout << "Данная программа находит все натуральные числа, которые можно представить в виде произведения двух простых чисел и которые не превосходят введённое натуральное число N\n";
    short n = inputNumber();
    short* arrayOfCorrect = findingRequiredNumbers(n);
    outputNumber(n, arrayOfCorrect);
    return 0;
}