#include <iostream>
using namespace std;
bool checkNatural(int n, int k = 2);

int main()
{
    setlocale(0, "");
    int num = 0;
    cout << "Введiть число: ";
    cin >> num;
    if(checkNatural(num))
        cout << "Число просте!" << "\n";
    else
        cout << "Число НЕ просте!" << "\n";
    return 0;
}

bool checkNatural(int n, int k)
{
    if (n < 2u)
        return false;
    else if (n == k)
        return true;
    else if (n % k)
        return checkNatural(n, k + 1);
    else
        return false;
}