/*
 * Лабораторная №1
 * Проверить число на простоту.
*/

#include <iostream>
#include <cmath>
#include <list>

using namespace std;

void simpleNumb(int n)
{
    bool flag = true;
    for (int i = 2; i <= n; i++) { // N
        if (n % i == 0 && i != n) { // N
            flag = false; //
            break; //
        }
    }
    // Result: O(N)
    flag ? cout << "Simple!\n" : cout << "Not simple!\n";
}

void simpleNumb2(int n)
{
    bool flag = true;
    for (int i = 2; i <= sqrt((float)n); i++) { // sqrt(N)
        if (n % i == 0) { // sqrt(N)
            flag = false; //
            break; //
        }
    }
    // Result: O(sqrt(N))
    flag ? cout << "Simple!\n" : cout << "Not simple!\n";
}

void simpleNumbFinal(int n)
{
    list<int> div;
    div.push_back(2);

    for (int i = 3; i < n + 1; i += 2)
    {
        for (list<int>::iterator j = div.begin(); j != div.end(); j++)
        {
            if (*j > float(sqrt(i)))
            {
                div.push_back(i);
                break;
            }
            else if (i % *j == 0)
                break;
        }
    }

    for (list<int>::iterator i = div.begin(); i != div.end(); i++)
        cout << *i << ' ';
}

int main()
{
    simpleNumb(56783);
    simpleNumb2(56783);
    simpleNumbFinal(56791);
    return 0;
}