Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 15, средняя оценка - 4.87
Naudiz
14 / 12 / 1
Регистрация: 04.11.2011
Сообщений: 137
#1

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

09.07.2013, 17:31. Просмотров 2321. Ответов 42
Метки нет (Все метки)

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

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

"Натуральное число называется совершенным, если оно равно сумме всех своих делителей, за исключением себя самого. Число 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;
}
Ссылки на литературу по сабжу приветствуются.

Заранее всем благодарен))
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
09.07.2013, 17:31
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Алгоритм проверки числа на "совершенность" (C++):

В зависимости от времени года "весна", "лето", "осень", "зима" определить погоду "тепло", "жарко", "холодно", "очень холодно" - C++
В зависимости от времени года &quot;весна&quot;, &quot;лето&quot;, &quot;осень&quot;, &quot;зима&quot; определить погоду &quot;тепло&quot;, &quot;жарко&quot;, &quot;холодно&quot;, &quot;очень холодно&quot;. Я так...

Наследуемым классом для комплексного числа объявить класс "радиус-вектор", имеющий данные "длина" и "угол" - C++
кто то напишите пожалуйста, вот программа: наследуемым классом для комплексного числа объявить класс &quot;радиус-вектор&quot;, имеющий данные...

Через ООП: Дать для числа наименование: "рубль", "рубля", "рублей"; - C++
Помогите пожалуйста с задачей. Могу сделать ее просто, но надо через ООП и у меня не получается. Дано натуральное число N (N&lt;20),...

Реализовать классы "Воин", "Пехотинец", "Винтовка", "Матрос", "Кортик" (наследование) - C++
Разработать программу с использованием наследования классов, реализующую классы: − воин; − пехотинец(винтовка); − матрос(кортик). ...

Создать абстрактный класс "Издание" и производные классы "Книга", "Статья", "Электронный ресурс" - C++
1. Создать абстрактный класс Издание с методами, позволяющими вывести на экран информацию об издании, а также определить является ли данное...

Создать класс "Книга" с полями "название книги", "количество страниц", "год издания" - C++
Создать класс Книга поля: название книги,количество страниц,год издания методы: вычислить сколько лет книге и количество дней прошедших...

42
Dani
1393 / 637 / 57
Регистрация: 11.08.2011
Сообщений: 2,295
Записей в блоге: 2
Завершенные тесты: 1
12.07.2013, 20:57 #31
Самый быстрый поиск совершенных чисел. Берем гугл. Сбиваем "OEIS совершенные числа". Находим эту страницу - http://oeis.org/A000396 Копируем все числа в константы (хоть в строковые). Организуем поиск по константам. Радуемся сложности O(1)
0
Naudiz
14 / 12 / 1
Регистрация: 04.11.2011
Сообщений: 137
12.07.2013, 21:03  [ТС] #32
Thinker, не понял. В Вашем коде именно llu и он компилируется и работает))

Добавлено через 45 секунд
Dani, не смешно.
0
Thinker
Эксперт С++
4231 / 2205 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
12.07.2013, 21:04 #33
Цитата Сообщение от Naudiz Посмотреть сообщение
Thinker, не понял. В Вашем коде именно llu и он компилируется и работает))
тогда оставьте. ull нужно для работы с огромными типизированными константами, в противном случае число 50...0 просто урежется.
0
Dani
1393 / 637 / 57
Регистрация: 11.08.2011
Сообщений: 2,295
Записей в блоге: 2
Завершенные тесты: 1
12.07.2013, 21:07 #34
Цитата Сообщение от 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;
}
0
Thinker
Эксперт С++
4231 / 2205 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
12.07.2013, 21:12 #35
Dani, программа дает иллюзию, что что ты сам их находишь
0
Dani
1393 / 637 / 57
Регистрация: 11.08.2011
Сообщений: 2,295
Записей в блоге: 2
Завершенные тесты: 1
12.07.2013, 21:13 #36
Thinker, Зато 10 чисел найдет В отличии от других программ.
0
Naudiz
14 / 12 / 1
Регистрация: 04.11.2011
Сообщений: 137
12.07.2013, 21:15  [ТС] #37
Dani, речь идёт именно об "алгоритме проверки числа на совершенность", а не о выводе совершенных чисел на экран.

Thinker, а что происходит в 57 строке? Заранее извиняюсь, мне еще не по зубам такой код(
0
Dani
1393 / 637 / 57
Регистрация: 11.08.2011
Сообщений: 2,295
Записей в блоге: 2
Завершенные тесты: 1
12.07.2013, 21:16 #38
Naudiz, здесь и проверяется число на совершенность, как ты мог заметить.
0
Thinker
Эксперт С++
4231 / 2205 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
12.07.2013, 21:19 #39
Dani, программа дает иллюзию, что если вдруг ОЗУ позволит хранить очень большие числа, то с ее помощью можно найти еще несколько дополнительных чисел, не вошедших в ТОП10

Добавлено через 2 минуты
Цитата Сообщение от Naudiz Посмотреть сообщение
Thinker, а что происходит в 57 строке?
это просто. с помощью побитовых операций вычисляем значение
http://www.cyberforum.ru/cgi-bin/latex.cgi?2^{i-1}(2^i-1)
0
Dani
1393 / 637 / 57
Регистрация: 11.08.2011
Сообщений: 2,295
Записей в блоге: 2
Завершенные тесты: 1
12.07.2013, 21:23 #40
Цитата Сообщение от Thinker Посмотреть сообщение
программа дает иллюзию
но она ведь правильно проверяет число на совершенность. что и требовалось
Цитата Сообщение от Naudiz Посмотреть сообщение
нужно чтобы программа требовала, как можно меньше памяти и работала быстрее.
Что ТС просил - все условия выполняются.
Если нужно научиться находить совершенные числа или в учебных целях - то с твоим кодом никто не конкурирует, но пусть большие числа считает, например, этот сайт http://oddperfect.org/
Да и BigInt юзать как-то неохота в связи с затратами и повышением сложности кода.
1
Naudiz
14 / 12 / 1
Регистрация: 04.11.2011
Сообщений: 137
12.07.2013, 21:25  [ТС] #41
Thinker, опять же
C++
1
sov = ((1llu << i) - 1llu) << (i - 1llu);
Что такое "1llu"? Какое значение оно принимает?
0
Dani
1393 / 637 / 57
Регистрация: 11.08.2011
Сообщений: 2,295
Записей в блоге: 2
Завершенные тесты: 1
12.07.2013, 21:27 #42
Naudiz, оно делает приведение типа к unsigned long long.
1
Thinker
Эксперт С++
4231 / 2205 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
12.07.2013, 21:30 #43
Цитата Сообщение от Naudiz Посмотреть сообщение
Thinker, опять же
C++
1
sov = ((1llu << i) - 1llu) << (i - 1llu);
Что такое "1llu"? Какое значение оно принимает?
ull говорит компилятору, что мы работаем с очень большими числами, иначе компилятор их обрежет и результат будет неверным.

Добавлено через 2 минуты
Цитата Сообщение от Dani Посмотреть сообщение
с твоим кодом никто не конкурирует

Не по теме:

с этого надо было начинать

2
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.07.2013, 21:30
Привет! Вот еще темы с ответами:

Создать класс "Вентилятор" содержащий в себе классы: "Двигатель", "Контроллер", "Пульт управления" - C++
Помогите с кодом написания задачи, не понимаю как написать классы в классе. Нужно создать класс &quot;вентилятор&quot; содержащий в себе классы:...

Дано натуральное число. Найти сумму последних "n" цифр "n" числа, не применяя переменых значений - C++
Здравствуйте, помогите написать две программы. 1) Дано натуральное число. Найти сумму последних &quot;n&quot; цифр &quot;n&quot; числа, не применяя...

Нужно сделать так, чтобы при вводе числа, выводило "рублей" или "рубль" - C++
Начал решать задачу и засох на средине, не выходить формулу написать,если не сложно,подскажите) с с++ знаю пока что if,else и swith) //...

2 Программы. На "целые числа и системы счисления" и на "метод деления отрезка пополам" - C++
1)Дано натурально число n. Среди чисел 1, ... ,n найти все такие, запись которых совпадает с последними цифрами их квадрата ( как,...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
43
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru