С наступающим Новым годом! Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 4.77/13: Рейтинг темы: голосов - 13, средняя оценка - 4.77
Naudiz
15 / 13 / 7
Регистрация: 04.11.2011
Сообщений: 137
1

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

09.07.2013, 17:31. Просмотров 2608. Ответов 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
Ответы с готовыми решениями:

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

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

Через ООП: Дать для числа наименование: "рубль", "рубля", "рублей";
Помогите пожалуйста с задачей. Могу сделать ее просто, но надо через ООП и у...

Для каждой строки найти слова, которые не имеют ни одного из букв: "l", "k", "r", "s" i "j"
Задано символьные строки. Строка состоит из нескольких слов (наборов символов),...

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

42
jurok_85
275 / 258 / 190
Регистрация: 21.02.2013
Сообщений: 617
Завершенные тесты: 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
Модератор
7376 / 5576 / 708
Регистрация: 14.02.2011
Сообщений: 18,959
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
1150 / 867 / 90
Регистрация: 03.08.2011
Сообщений: 2,404
Завершенные тесты: 1
09.07.2013, 18:55 4
Naudiz, для начала предложу считать до x/2, так как числа больше половины не могут быть делителями. Сумму можно сразу начинать с 1, а делители искать с 2.

ADD: Чуть опоздал.
0
Kukurudza
105 / 86 / 13
Регистрация: 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
Эксперт С++
4234 / 2208 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
09.07.2013, 19:35 6
Цитата Сообщение от Toshkarik Посмотреть сообщение
для начала предложу считать до x/2
правильно, но еще лучше до корня из числа
Быстрое нахождение количества делителей натурального числа
посты #4 и #5
1
Toshkarik
1150 / 867 / 90
Регистрация: 03.08.2011
Сообщений: 2,404
Завершенные тесты: 1
09.07.2013, 19:37 7
Thinker, почему же до корня? Ищем ведь не простые числа. К примеру возьмем 100. Корень == 10, но как же 20, 25 и 50?
0
Thinker
Эксперт С++
4234 / 2208 / 203
Регистрация: 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
Модератор
7376 / 5576 / 708
Регистрация: 14.02.2011
Сообщений: 18,959
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
Эксперт С++
4234 / 2208 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
09.07.2013, 19:42 11
Цитата Сообщение от ValeryS Посмотреть сообщение
фиг вам
смотри пост #8
0
Toshkarik
1150 / 867 / 90
Регистрация: 03.08.2011
Сообщений: 2,404
Завершенные тесты: 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
Модератор
7376 / 5576 / 708
Регистрация: 14.02.2011
Сообщений: 18,959
09.07.2013, 19:47 13
посмотрел ничего не понял
Цитата Сообщение от Thinker Посмотреть сообщение
на 4 делится, значит и на 100/4=25 тоже делится
что делится ? 10?
и потом покажи как ты сумму делителей считать будешь?
да и 100 не совершенное число
1+2+4+5+10+20+25+50=117
0
Toshkarik
1150 / 867 / 90
Регистрация: 03.08.2011
Сообщений: 2,404
Завершенные тесты: 1
09.07.2013, 19:48 14
ValeryS, Вы не поняли смысла. 6 / 2 == 3. И 2 и 3 являются делителями.
0
Thinker
Эксперт С++
4234 / 2208 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
09.07.2013, 19:49 15
Цитата Сообщение от ValeryS Посмотреть сообщение
и потом покажи как ты сумму делителей считать будешь?
http://www.cyberforum.ru/post3547206.html

Цитата Сообщение от 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
Kukurudza
105 / 86 / 13
Регистрация: 29.08.2012
Сообщений: 539
09.07.2013, 19:55 16
Thinker, ваш алгоритм работает за n^0.5, если я не ошибаюсь. нотация снизилась до n^(3/2). если я введу число с 20 нулями, ждать вы будете до второго пришествия
0
ValeryS
Модератор
7376 / 5576 / 708
Регистрация: 14.02.2011
Сообщений: 18,959
09.07.2013, 19:58 17
тут можно добавить еще одно условие и изменить направление
C++
1
2
3
4
5
for (int i= x/2; i>0; i--)
{
  if (x%i==0) sum+=i;
 if (sum>x) break;
}
при больших количествах делителей цикл будет работать не до конца
например для 100
50+25+20+10 вылетит
можно до корня ну тогда цикл будет сложный
что то типа
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int sum=1;
int n=sqrt(x);
for(int i=2;i<=n;i++)
{
if(x%i==0)
 {
  if(i==n)
    sum+=i;
  else
   {
      sum+=i;
      sum+=x/i;
   }
 }

}
0
Thinker
Эксперт С++
4234 / 2208 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
09.07.2013, 19:59 18
Kukurudza, мы немного абстрагировались от совершенных чисел, речь о сумме делителей натурального числа. и Вы правильно поняли сложность алгоритма.

Но что касается совершенных чисел, то это понятно, что их по-другому проверяют
Получить совершенные числа
посты #3 и #4
0
Toshkarik
1150 / 867 / 90
Регистрация: 03.08.2011
Сообщений: 2,404
Завершенные тесты: 1
09.07.2013, 20:02 19
Thinker, так скорей всего Ваш код и будет быстрее, так как операция деления довольно дорогая.
0
Kukurudza
105 / 86 / 13
Регистрация: 29.08.2012
Сообщений: 539
09.07.2013, 20:04 20
Toshkarik на самом деле на сегодняшний момент операция деления такая же по стоимости как и умножение. как она реадизована я не в курсе в современных процессорах. я лично проверял на i5 процессоре.
0
09.07.2013, 20:04
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.07.2013, 20:04

Дано ошибочно написанное слово "алигортм". Путем перемещения его букв получить слово "алгоритм"
9.129. Дано ошибочно написанное слово алигортм. Путем перемещения его букв...

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

Создать класс "Книга" с полями "название книги", "количество страниц", "год издания"
Создать класс Книга поля: название книги,количество страниц,год издания...


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

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

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