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

@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] Алгоритм «Хак Госпера» alhaos 17.05.2026 Алгоритм «Хак Госпера» Хак Госпера (Gosper's Hack) — алгоритм нахождения следующего по величине числа с тем же количеством установленных бит. Придуман Биллом Госпером в 1970-х, опубликован в. . .	Рисование бинарного древа до 6-го колена на js, svg. russiannick 17.05.2026 <svg width="335" height="240" viewBox="0 0 335 240" fill="#e5e1bb"> <style> <!]> </ style> <g id="bush"> </ g> </ svg> function fn(){ let rost;/ / высота древа let xx=165,yy=210,w=256;	FSharp: interface of module DevAlt 16.05.2026 Интерфейс модуля F# позволяет управлять доступностью членов, содержащихся в реализации модуля. По-умолчанию все члены модуля доступны: module Foo let x = 10 let boo () = printfn "boo" . . .	Хитросплетение родственных связей пантеона греческих богов. russiannick 14.05.2026 Однооконник, позволяющий узреть и изучить отдельных героев древней Греции. <!DOCTYPE html> <html lang="ru"> <head> <meta charset="UTF-8"> <meta http-equiv="X-UA-Compatible". . .
[golang] Угол между стрелками часов alhaos 12.05.2026 По заданным значениям часа и минуты необходимо определить значение меньшего угла между стрелками аналогового циферблата часов. import "math" func angleClock(hour int, minutes int) float64 { . . .	Debian 13: Установка Lazarus QT5 ВитГо 09.05.2026 Эта инструкция моя компиляция инструкций volvo https:/ / www. cyberforum. ru/ blogs/ 203668/ 10753. html и его же старой инструкции по установке Lazarus с gtk2. . .	Нейросеть на алгоритме "эстафета хвоста" как перспектива. Hrethgir 06.05.2026 На десерт, когда запущу сервер. Статья тут https:/ / habr. com/ ru/ articles/ 1030914/ . Автор я сам, нейросеть только помогает в вопросах которые мне не известны - не знаю людей которые знали-бы. . .	Асинхронный приём данных из COM-порта Argus19 01.05.2026 Асинхронный приём данных из COM-порта Купил на aliexpress термопринтер QR701. Он оказался странным. Поключил к Arduino Nano. Был очень удивлён. Наотрез отказывается печатать русские буквы. Чтобы. . .

@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