//Лабораторная работа на нахождение совершенных чисел.
//Выполнила Инна Васильева

#include<iostream>
#include<vector>
#include<time.h>
using namespace std;

int main() {

    int n;
    cout << "Enter the upper bound:\n";
    cin >> n;

    //удобный динамический массив(и список при необходимости)
    vector<int>arr;

    //задаем длинну и заполняем int(1)
    arr.assign(n+1, 1);

    cout << "Perfect numbers:\n";

    //засекаем время
    clock_t tStart = clock();

    //используя алгоритм аналогичный решету эратосфена
    //подсчитываем в каждом числе сумму его делителей
    //используя принцип динамического программирования
    for (int i = 2; i < arr.size(); i++) {
        //если сумма делителей совпала с числом - оно совершенное выводим
        if (arr[i] == i)
            cout << i << endl;

        //от каждого числа проходимся по его делителям
        //и добавляем это число в их счетчики
        for (int j = i + i; j < n; j += i) {
            arr[j] += i;
        }
    }

    //выводим время выполнения
    printf("Time taken: %.2fs\n", (double)(clock() - tStart) / CLOCKS_PER_SEC);
}