Алгоритм проверки числа на "совершенность"

@Naudiz · Регистрация: 04.11.2011

Приветствую всех!

Прошу помочь со следующей задачей:

"Натуральное число называется совершенным, если оно равно сумме всех своих делителей, за исключением себя самого. Число 6 – совершенное, так как 6 = 1+2+3. Число 8 – не совершенное, так как 8 ≠ 1+2+4.Дано натуральное число n. Получить все совершенные числа, меньшие n."

Задачу я решил (код ниже), но работает программа слишком медленно. Пожалуйста помогите оптимизировать код, нужно чтобы программа требовала, как можно меньше памяти и работала быстрее.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
 
using namespace std;
 
bool perfect(int x)
{
   int sum=0;
   for (int i=1; i<x; i++)
      if (x%i==0) sum+=i;
   if (x==sum) return 1;
   return 0;
}
 
int main()
{
   int x;
   cin >> x;
   for (int i=1; i<=x; i++)
      if (perfect(i)) cout << i << endl;
   return 0;
}

Ссылки на литературу по сабжу приветствуются.

Заранее всем благодарен))

@Thinker · 09.07.2013, 20:04

Сообщение от Toshkarik

Thinker, так скорей всего Ваш код и будет быстрее, так как операция деления довольно дорогая.

Спасибо, что понимаете

в том алгоритме по сути не используется свойство:
если a делитель n, то и n/a тоже делитель, там еще более крутые моменты (мультипликативные функции), поэтому быстро работает

P.S. а то бы не выставлял бы тот алгоритм. интересно было поработать с мульт.функциями, после чего пришла идея такого алгоритма.

ValeryS · 09.07.2013, 20:18

Сообщение от Kukurudza

Toshkarik на самом деле на сегодняшний момент операция деления такая же по стоимости как и умножение.

не совсем уверен

i5 нет проверить не могу
но до него div достаточно дорогая операция была

Сообщение от Kukurudza

как она реадизована я не в курсе

очень часто деление заменяется на умножение и сдвиг

@Toshkarik · 09.07.2013, 20:23

Kukurudza, я что то разве говорил об умножении? Я сравнивал с битовыми операциями.

@Naudiz · 10.07.2013, 09:36 **[ТС]**

ValeryS, спасибо за замечания)) Сразу как-то и не подумал над х/2.
Чуть-чуть причесал код:

Кликните здесь для просмотра всего текста

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
 
bool perfect(unsigned int x)
{
   unsigned int sum=0;
   for (int i=1; i<=x/2; i++)
      if (x%i==0) sum+=i;
   return x==sum;
}
 
int main()
{
   unsigned int x;
   std::cin >> x;
   for (unsigned int i=4; i<=x; i++)
      if (perfect(i)) std::cout << i << std::endl;
   return 0;
}

Kukurudza, благодарю за вики, появились кое какие мысли) Использование последовательности чисел Мерсенне способ весьма годный на практике, но когда речь идёт об алгоритмизации думаю не совсем уместен.

Сообщение от Kukurudza

реализованный алгоритм имеет нотацию O(n*n)

Это оценка скорости выполнения или количества операций алгоритма? Можно подробнее?

Thinker, Ваш алгоритм нахождения делителей числа действительно очень быстро работает. Еще не разобрался как он работает...

Вообщем по алгоритму проверки числа на совершенность пока идей больше нет, а вот как сократить количество итераций проверки самих чисел меньше заданного n (по условию) есть. Заинтересовало сл. св-во совершенных чисел в вики:
"Все чётные совершенные числа в двоичной записи содержат сначала p единиц, за которыми следует p—1 нулей (следствие из их общего представления)."

Таким образом можно было бы проверять все числа от 4 до n сначала на удовлетворение этому условию (операция, как я полагаю, менее затратная, если не ошибаюсь) и только проходящие по нему проверять на совершенность.

@Thinker · 10.07.2013, 09:39

Сообщение от Naudiz

Thinker, Ваш алгоритм нахождения делителей числа действительно очень быстро работает. Еще не разобрался как он работает...

Спасибо, всякую фигню бы не стал выставлять на показ

Возможно, оптимизирую его как-нибудь.

@Kukurudza · 10.07.2013, 10:02

Сообщение от Naudiz

Это оценка скорости выполнения или количества операций алгоритма? Можно подробнее?

ей богу, у меня иногда складывается мнение что только у меня гугл разбанен:
http://ru.wikipedia.org/wiki/%... 0%B8%D1%8F
а вообще это у вас академическая задача или какая-то практическая? решили нобеля получить поди?

@Stereotip · 10.07.2013, 10:17

если интересно разобраться с О( ) и с другими её друзьями - "Алгоритмы построения и анализ" авторы: Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн)

@Thinker · 10.07.2013, 12:31

Naudiz,
Быстрый поиск совершенных чисел

@Naudiz · 12.07.2013, 20:50 **[ТС]**

Thinker, благодарю, то что нужно. Можно вопрос по Вашему коду?

C++
1
const unsigned long long N = 5000000000000000000llu; //3я строка

Что значит "llu"?

Эта запись в дальнейшем фигурирует в выражениях в main

@Thinker · 12.07.2013, 20:53

Сообщение от Naudiz

Что значит "llu"?

Эта запись в дальнейшем фигурирует в выражениях в main

везде llu замените на ull это константа типа unsigned long long

@Dani · 12.07.2013, 20:57

Самый быстрый поиск совершенных чисел. Берем гугл. Сбиваем "OEIS совершенные числа". Находим эту страницу - http://oeis.org/A000396 Копируем все числа в константы (хоть в строковые). Организуем поиск по константам. Радуемся сложности O(1)

@Naudiz · 12.07.2013, 21:03 **[ТС]**

Thinker, не понял. В Вашем коде именно llu и он компилируется и работает))

Добавлено через 45 секунд
Dani, не смешно.

@Thinker · 12.07.2013, 21:04

Сообщение от Naudiz

Thinker, не понял. В Вашем коде именно llu и он компилируется и работает))

тогда оставьте. ull нужно для работы с огромными типизированными константами, в противном случае число 50...0 просто урежется.

@Dani · 12.07.2013, 21:07

Сообщение от Naudiz

Dani, не смешно.

Никто шутить и не собирался. Работает быстро и правильно.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>
#include <string>
#include <algorithm>
 
int main()
{
    const std::string arr[] = {"6","28","496","8128","33550336","8589869056","137438691328","2305843008139952128","2658455991569831744654692615953842176",
        "191561942608236107294793378084303638130997321548169216"}; //совершенные числа
    const int len = 10; //количество совершенных чисел
    std::string inp_number;
    std::cin >> inp_number;
    std::cout << ( std::find(arr, arr+len, inp_number) != arr+len ? "It is perfect number" : "It is not perfect number") << std::endl;
    return 0;
}

@Thinker · 12.07.2013, 21:12

Dani, программа дает иллюзию, что что ты сам их находишь

@Dani · 12.07.2013, 21:13

Thinker, Зато 10 чисел найдет

В отличии от других программ.

@Naudiz · 12.07.2013, 21:15 **[ТС]**

Dani, речь идёт именно об "алгоритме проверки числа на совершенность", а не о выводе совершенных чисел на экран.

Thinker, а что происходит в 57 строке? Заранее извиняюсь, мне еще не по зубам такой код(

@Dani · 12.07.2013, 21:16

Naudiz, здесь и проверяется число на совершенность, как ты мог заметить.

@Thinker · 12.07.2013, 21:19

Dani, программа дает иллюзию, что если вдруг ОЗУ позволит хранить очень большие числа, то с ее помощью можно найти еще несколько дополнительных чисел, не вошедших в ТОП10

Добавлено через 2 минуты

Сообщение от Naudiz

Thinker, а что происходит в 57 строке?

это просто. с помощью побитовых операций вычисляем значение
$https://www.cyberforum.ru/cgi-bin/latex.cgi?2^{i-1}(2^i-1)$

@Dani · 12.07.2013, 21:23

Сообщение от Thinker

программа дает иллюзию

но она ведь правильно проверяет число на совершенность. что и требовалось

Сообщение от Naudiz

нужно чтобы программа требовала, как можно меньше памяти и работала быстрее.

Что ТС просил - все условия выполняются.
Если нужно научиться находить совершенные числа или в учебных целях - то с твоим кодом никто не конкурирует, но пусть большие числа считает, например, этот сайт http://oddperfect.org/
Да и BigInt юзать как-то неохота в связи с затратами и повышением сложности кода.

Новые блоги и статьи Все статьи Все блоги /
[golang] Конкурентный fetcher с ограничением максимального количества одновременных HTTP запросов. alhaos 10.06.2026 Задача Реализовать конкурентный fetcher с ограничением максимального количества одновременных HTTP запросов. Сигнатура func Fetch(urls string, maxConcurrent int) Result Пример urls :=. . .	[golang] Состояние гонки (race condition) alhaos 10.06.2026 Состояние гонки (race condition) Состояние гонки (Race Condition) — это ошибка, возникающая при одновременном доступе нескольких горутин к одним и тем же данным без должной синхронизации. При этом. . .	Взрослые отношения, и почему они не получаются kumehtar 09.06.2026 Когда в детстве ребёнок не получает от родителей чего-то важного, он лишается не просто приятных переживаний, а основы для формирования определённых внутренних качеств и навыков. Если ребёнок не. . .	[golang] Worker Pool alhaos 09.06.2026 Worker Pool Worker Pool — паттерн конкурентной обработки задач в Go. Суть: фиксированное количество горутин-воркеров читают задачи из общего канала и пишут результаты в общий канал результатов. . . .
[golang] Pipeline alhaos 08.06.2026 Pipeline Pipeline — паттерн конкурентной обработки данных в Go. Суть: данные проходят через цепочку независимых стадий, каждая из которых работает в своей горутине и общается с соседями через. . .	Свет внутри себя kumehtar 07.06.2026 Пусть это будет здесь lIs4oanZS9Y	Программа для com-порта Uhbif79 05.06.2026 Всем привет, давно хотел изучить Qt, начинал, бросал, потом снова начинал. И сейчас вот смог написать свою первую программу. До этого имел опыт программирования микроконтроллеров, писал прошивки на. . .	Транскрипция 55-минутного видео через Whisper: WhisperDesktop облажался, спас Google Colab[ anaschu 01.06.2026 Понадобилось получить текст из свежезагруженного видео на YouTube. Казалось бы, задача на пять минут. Заняла полтора часа. Делюсь опытом — может кому пригодится последовательность решений. . . .

@Toshkarik 1181 / 894 / 94 Регистрация: 03.08.2011 Сообщений: 2,461
	09.07.2013, 20:23
	Kukurudza, я что то разве говорил об умножении? Я сравнивал с битовыми операциями. 0

@Stereotip 2 / 2 / 1 Регистрация: 17.04.2012 Сообщений: 22
	10.07.2013, 10:17
	если интересно разобраться с О( ) и с другими её друзьями - "Алгоритмы построения и анализ" авторы: Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн) 1

@Thinker 4267 / 2241 / 203 Регистрация: 26.08.2011 Сообщений: 3,802 Записей в блоге: 5
	10.07.2013, 12:31
	Naudiz, Быстрый поиск совершенных чисел 0

@Dani 1406 / 648 / 135 Регистрация: 11.08.2011 Сообщений: 2,299 Записей в блоге: 2
	12.07.2013, 20:57
	Самый быстрый поиск совершенных чисел. Берем гугл. Сбиваем "OEIS совершенные числа". Находим эту страницу - http://oeis.org/A000396 Копируем все числа в константы (хоть в строковые). Организуем поиск по константам. Радуемся сложности O(1) 0

@Naudiz 16 / 14 / 7 Регистрация: 04.11.2011 Сообщений: 137
	12.07.2013, 21:03 [ТС]
	Thinker, не понял. В Вашем коде именно llu и он компилируется и работает)) Добавлено через 45 секунд Dani, не смешно. 0

@Thinker 4267 / 2241 / 203 Регистрация: 26.08.2011 Сообщений: 3,802 Записей в блоге: 5
	12.07.2013, 21:12
	Dani, программа дает иллюзию, что что ты сам их находишь 0

@Dani 1406 / 648 / 135 Регистрация: 11.08.2011 Сообщений: 2,299 Записей в блоге: 2
	12.07.2013, 21:13
	Thinker, Зато 10 чисел найдет В отличии от других программ. 0

@Naudiz 16 / 14 / 7 Регистрация: 04.11.2011 Сообщений: 137
	12.07.2013, 21:15 [ТС]
	Dani, речь идёт именно об "алгоритме проверки числа на совершенность", а не о выводе совершенных чисел на экран. Thinker, а что происходит в 57 строке? Заранее извиняюсь, мне еще не по зубам такой код( 0

@Dani 1406 / 648 / 135 Регистрация: 11.08.2011 Сообщений: 2,299 Записей в блоге: 2
	12.07.2013, 21:16
	Naudiz, здесь и проверяется число на совершенность, как ты мог заметить. 0