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

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

Author24 — интернет-сервис помощи студентам

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

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

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

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

C++

#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++

#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++

#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 юзать как-то неохота в связи с затратами и повышением сложности кода.

ValeryS Модератор 8909 / 6678 / 918 Регистрация: 14.02.2011 Сообщений: 23,524
	09.07.2013, 20:18	22
	Сообщение от Kukurudza Toshkarik на самом деле на сегодняшний момент операция деления такая же по стоимости как и умножение. не совсем уверен i5 нет проверить не могу но до него div достаточно дорогая операция была Сообщение от Kukurudza как она реадизована я не в курсе очень часто деление заменяется на умножение и сдвиг 0

@Thinker 4267 / 2241 / 203 Регистрация: 26.08.2011 Сообщений: 3,802 Записей в блоге: 5
	10.07.2013, 09:39	25
	Сообщение от Naudiz Thinker, Ваш алгоритм нахождения делителей числа действительно очень быстро работает. Еще не разобрался как он работает... Спасибо, всякую фигню бы не стал выставлять на показ Возможно, оптимизирую его как-нибудь. 0

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

@Dani 1405 / 647 / 135 Регистрация: 11.08.2011 Сообщений: 2,299 Записей в блоге: 2
	12.07.2013, 21:23	40
	Сообщение от Thinker программа дает иллюзию но она ведь правильно проверяет число на совершенность. что и требовалось Сообщение от Naudiz нужно чтобы программа требовала, как можно меньше памяти и работала быстрее. Что ТС просил - все условия выполняются. Если нужно научиться находить совершенные числа или в учебных целях - то с твоим кодом никто не конкурирует, но пусть большие числа считает, например, этот сайт http://oddperfect.org/ Да и BigInt юзать как-то неохота в связи с затратами и повышением сложности кода. 1

@Thinker 4267 / 2241 / 203 Регистрация: 26.08.2011 Сообщений: 3,802 Записей в блоге: 5
	09.07.2013, 20:04	21
	Сообщение от Toshkarik Thinker, так скорей всего Ваш код и будет быстрее, так как операция деления довольно дорогая. Спасибо, что понимаете в том алгоритме по сути не используется свойство: если a делитель n, то и n/a тоже делитель, там еще более крутые моменты (мультипликативные функции), поэтому быстро работает P.S. а то бы не выставлял бы тот алгоритм. интересно было поработать с мульт.функциями, после чего пришла идея такого алгоритма. 0

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

@Kukurudza 106 / 87 / 13 Регистрация: 29.08.2012 Сообщений: 539
	10.07.2013, 10:02	26
	Сообщение от Naudiz Это оценка скорости выполнения или количества операций алгоритма? Можно подробнее? ей богу, у меня иногда складывается мнение что только у меня гугл разбанен: http://ru.wikipedia.org/wiki/%... 0%B8%D1%8F а вообще это у вас академическая задача или какая-то практическая? решили нобеля получить поди? 0

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

@Thinker 4267 / 2241 / 203 Регистрация: 26.08.2011 Сообщений: 3,802 Записей в блоге: 5
	12.07.2013, 20:53	30
	Сообщение от Naudiz Что значит "llu"? Эта запись в дальнейшем фигурирует в выражениях в main везде llu замените на ull это константа типа unsigned long long 0

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

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

@Thinker 4267 / 2241 / 203 Регистрация: 26.08.2011 Сообщений: 3,802 Записей в блоге: 5
	12.07.2013, 21:04	33
	Сообщение от Naudiz Thinker, не понял. В Вашем коде именно llu и он компилируется и работает)) тогда оставьте. ull нужно для работы с огромными типизированными константами, в противном случае число 50...0 просто урежется. 0

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

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

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

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

@Thinker 4267 / 2241 / 203 Регистрация: 26.08.2011 Сообщений: 3,802 Записей в блоге: 5
	12.07.2013, 21:19	39
	Dani, программа дает иллюзию, что если вдруг ОЗУ позволит хранить очень большие числа, то с ее помощью можно найти еще несколько дополнительных чисел, не вошедших в ТОП10 Добавлено через 2 минуты Сообщение от Naudiz Thinker, а что происходит в 57 строке? это просто. с помощью побитовых операций вычисляем значение $https://www.cyberforum.ru/cgi-bin/latex.cgi?2^{i-1}(2^i-1)$ 0