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

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

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

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

09.07.2013, 17:31. Просмотров 2155. Ответов 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
jurok_85
241 / 225 / 78
Регистрация: 21.02.2013
Сообщений: 520
Завершенные тесты: 1
09.07.2013, 18:38 #2
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
 
void perfect();
 
using namespace std;
 
int main()
{
   perfect();
   
   return 0;
}
 
void perfect()
{
   int sum = 0;
   
   for(int number = 1; number <= 1000; number++)
   {
      for(int j = 1; j < number; j++)
      {
         if(number % j == 0)
            sum += j;
      }
      
      if(number == sum)
      {
         cout << "Chislo " << number << " sovershennoye!!!" << endl;
         cout << "Ego somnoshiteli: ";
         
         for(int i = 1; i < number; i++)
            if(number % i == 0)
               cout << i << "; ";
               
         cout << endl << endl;
      }
      
      sum = 0;
   }
}
0
ValeryS
Модератор
6709 / 5118 / 482
Регистрация: 14.02.2011
Сообщений: 17,213
09.07.2013, 18:54 #3
Цитата Сообщение от Naudiz Посмотреть сообщение
if (x==sum) return 1;
* *return 0;
вот это можешь заменить на
C++
1
return x==summ;
Цитата Сообщение от Naudiz Посмотреть сообщение
for (int i=1; i<x; i++)
* * * if (x%i==0) sum+=i;
количество итераций можешь уменьшить в два раза
больше чем x/2 делителей нет (ну кроме x, а он по условию не проходит)
C++
1
2
for (int i=1; i<=x/2; i++)
  if (x%i==0) sum+=i;
Добавлено через 3 минуты
Цитата Сообщение от Naudiz Посмотреть сообщение
for (int i=1; i<=x; i++)
* * * if (perfect(i)) cout << i << endl;
один два три можешь смело выбрасывать они простые значит не совершенные
начинай с 4
можешь еще добавить проверку на простоту, но вряд ли это ускорит выполнение
1
Toshkarik
1143 / 860 / 51
Регистрация: 03.08.2011
Сообщений: 2,390
Завершенные тесты: 1
09.07.2013, 18:55 #4
Naudiz, для начала предложу считать до x/2, так как числа больше половины не могут быть делителями. Сумму можно сразу начинать с 1, а делители искать с 2.

ADD: Чуть опоздал.
0
Kukurudza
105 / 86 / 6
Регистрация: 29.08.2012
Сообщений: 539
09.07.2013, 19:28 #5
господа, реализованный алгоритм имеет нотацию O(n*n). то что вы предлагаете сделает нотацию алгоритма O(n*n/2). это не выход. нужно алгоритм другой.

Добавлено через 5 минут
я бы предложил курнуть вики:
http://ru.wikipedia.org/wiki/Совершенное_число
решить в лоб может любой.
так же прочтите тему Определить, является ли заданное натуральное число совершенным сам не читал. но там что то про числа мерсенне - верный путь
1
Thinker
Эксперт С++
4228 / 2202 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
09.07.2013, 19:35 #6
Цитата Сообщение от Toshkarik Посмотреть сообщение
для начала предложу считать до x/2
правильно, но еще лучше до корня из числа
Быстрое нахождение количества делителей натурального числа
посты #4 и #5
1
Toshkarik
1143 / 860 / 51
Регистрация: 03.08.2011
Сообщений: 2,390
Завершенные тесты: 1
09.07.2013, 19:37 #7
Thinker, почему же до корня? Ищем ведь не простые числа. К примеру возьмем 100. Корень == 10, но как же 20, 25 и 50?
0
Thinker
Эксперт С++
4228 / 2202 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
09.07.2013, 19:38 #8
Цитата Сообщение от Toshkarik Посмотреть сообщение
Thinker, почему же до корня? Ищем ведь не простые числа. К примеру возьмем 100. Корень == 10, но как же 20, 25 и 50?
до 100. корень 10
на 2 делится, значит и на 100/2=50 тоже делится
на 4 делится, значит и на 100/4=25 тоже делится
на 5 делится, значит и на 100/5=20 тоже делится
0
betline
1 / 1 / 0
Регистрация: 27.06.2013
Сообщений: 26
09.07.2013, 19:40 #9
Цитата Сообщение от Kukurudza Посмотреть сообщение
господа, реализованный алгоритм имеет нотацию O(n*n). то что вы предлагаете сделает нотацию алгоритма O(n*n/2). это не выход. нужно алгоритм другой.

Добавлено через 5 минут
я бы предложил курнуть вики:
http://ru.wikipedia.org/wiki/Совершенное_число
решить в лоб может любой.
так же прочтите тему Определить, является ли заданное натуральное число совершенным сам не читал. но там что то про числа мерсенне - верный путь
Поддерживаю. Уже все давно решено. Вики и поиск - рулит.
0
ValeryS
Модератор
6709 / 5118 / 482
Регистрация: 14.02.2011
Сообщений: 17,213
09.07.2013, 19:41 #10
Цитата Сообщение от Thinker Посмотреть сообщение
правильно, но еще лучше до корня из числа
фиг вам
число 6
делители 1+2+3 =6
корень из числа 6 примерно 2,449
число 28
делители 1+2+4+7+14 =28
корень из числа 28 примерно 5.29
то что предложил это для простоты числа, если делителей меньше корня нет то и больше нет
0
Thinker
Эксперт С++
4228 / 2202 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
09.07.2013, 19:42 #11
Цитата Сообщение от ValeryS Посмотреть сообщение
фиг вам
смотри пост #8
0
Toshkarik
1143 / 860 / 51
Регистрация: 03.08.2011
Сообщений: 2,390
Завершенные тесты: 1
09.07.2013, 19:46 #12
Thinker, это то понятно. Но тогда придется делать лишнюю операцию умножения, скорость если и будет чуть больше, но не намного. У меня с самого начала была идея что вроде такой:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
bool isPerfect( unsigned int x ) {
   unsigned int sum = 1;
   unsigned int border = x / 2;
   unsigned int tmp;
   
   for ( unsigned int i = 2; i < border; i++ ) {
      tmp = x / i;
      
      if ( tmp * i == x ) {
         sum += i;
         sum += tmp;
         border = tmp;
      }
   }
   
   return sum == x;
}
0
ValeryS
Модератор
6709 / 5118 / 482
Регистрация: 14.02.2011
Сообщений: 17,213
09.07.2013, 19:47 #13
посмотрел ничего не понял
Цитата Сообщение от Thinker Посмотреть сообщение
на 4 делится, значит и на 100/4=25 тоже делится
что делится ? 10?
и потом покажи как ты сумму делителей считать будешь?
да и 100 не совершенное число
1+2+4+5+10+20+25+50=117
0
Toshkarik
1143 / 860 / 51
Регистрация: 03.08.2011
Сообщений: 2,390
Завершенные тесты: 1
09.07.2013, 19:48 #14
ValeryS, Вы не поняли смысла. 6 / 2 == 3. И 2 и 3 являются делителями.
0
Thinker
Эксперт С++
4228 / 2202 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
09.07.2013, 19:49 #15
Цитата Сообщение от ValeryS Посмотреть сообщение
и потом покажи как ты сумму делителей считать будешь?
Быстрое нахождение количества делителей натурального числа

Цитата Сообщение от Toshkarik Посмотреть сообщение
У меня с самого начала была идея что вроде такой:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
bool isPerfect( unsigned int x ) {
   unsigned int sum = 1;
   unsigned int border = x / 2;
   unsigned int tmp;
   
   for ( unsigned int i = 2; i < border; i++ ) {
      tmp = x / i;
      
      if ( tmp * i == x ) {
         sum += i;
         sum += tmp;
         border = tmp;
      }
   }
   
   return sum == x;
}
попробуйте сравнить по скорости с
сумма делителей
здесь есть небольшие хитрости и делители только нечетные проверяются, степени двойки выделяются с помощью битовых операций и т.д.
0
09.07.2013, 19:49
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.07.2013, 19:49
Привет! Вот еще темы с ответами:

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

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

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

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


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

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

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