Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
 
Рейтинг 4.87/47: Рейтинг темы: голосов - 47, средняя оценка - 4.87
16 / 14 / 7
Регистрация: 04.11.2011
Сообщений: 137
1

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

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

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

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

"Натуральное число называется совершенным, если оно равно сумме всех своих делителей, за исключением себя самого. Число 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
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
09.07.2013, 17:31
Ответы с готовыми решениями:

Проверка числа на совершенность
Задача: использовать функцию, которая определяет, является ли введённое число совершенным или нет +...

Реализовать эффективный алгоритм проверки числа на простоту и подсчета количества делителей натурального числа
Реализовать эффективный алгоритм проверки числа на простоту и подсчета количества делителей...

Алгоритм проверки делимости числа на 7
Предлагаю алгоритм проверки делимости числа на 7. Описание алгоритма и примеры его применения...

Быстрый алгоритм проверки числа на простоту
Я уже пробовал перебор делителей числа. public bool IsPrime(BigInteger number) { for (int...

Нужен алгоритм проверки большого числа на простоту
Нужен быстрый код, который проверит число типа BigInteger на простоту (простое это число или нет)....

42
365 / 321 / 219
Регистрация: 21.02.2013
Сообщений: 756
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
Модератор
Эксперт по электронике
8908 / 6677 / 918
Регистрация: 14.02.2011
Сообщений: 23,523
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
1181 / 894 / 94
Регистрация: 03.08.2011
Сообщений: 2,461
09.07.2013, 18:55 4
Naudiz, для начала предложу считать до x/2, так как числа больше половины не могут быть делителями. Сумму можно сразу начинать с 1, а делители искать с 2.

ADD: Чуть опоздал.
0
106 / 87 / 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
Эксперт С++
4267 / 2241 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
09.07.2013, 19:35 6
Цитата Сообщение от Toshkarik Посмотреть сообщение
для начала предложу считать до x/2
правильно, но еще лучше до корня из числа
Быстрое нахождение количества делителей натурального числа
посты #4 и #5
1
1181 / 894 / 94
Регистрация: 03.08.2011
Сообщений: 2,461
09.07.2013, 19:37 7
Thinker, почему же до корня? Ищем ведь не простые числа. К примеру возьмем 100. Корень == 10, но как же 20, 25 и 50?
0
Эксперт С++
4267 / 2241 / 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
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
Модератор
Эксперт по электронике
8908 / 6677 / 918
Регистрация: 14.02.2011
Сообщений: 23,523
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
Эксперт С++
4267 / 2241 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
09.07.2013, 19:42 11
Цитата Сообщение от ValeryS Посмотреть сообщение
фиг вам
смотри пост #8
0
1181 / 894 / 94
Регистрация: 03.08.2011
Сообщений: 2,461
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
Модератор
Эксперт по электронике
8908 / 6677 / 918
Регистрация: 14.02.2011
Сообщений: 23,523
09.07.2013, 19:47 13
посмотрел ничего не понял
Цитата Сообщение от Thinker Посмотреть сообщение
на 4 делится, значит и на 100/4=25 тоже делится
что делится ? 10?
и потом покажи как ты сумму делителей считать будешь?
да и 100 не совершенное число
1+2+4+5+10+20+25+50=117
0
1181 / 894 / 94
Регистрация: 03.08.2011
Сообщений: 2,461
09.07.2013, 19:48 14
ValeryS, Вы не поняли смысла. 6 / 2 == 3. И 2 и 3 являются делителями.
0
Эксперт С++
4267 / 2241 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
09.07.2013, 19:49 15
Цитата Сообщение от ValeryS Посмотреть сообщение
и потом покажи как ты сумму делителей считать будешь?
https://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
106 / 87 / 13
Регистрация: 29.08.2012
Сообщений: 539
09.07.2013, 19:55 16
Thinker, ваш алгоритм работает за n^0.5, если я не ошибаюсь. нотация снизилась до n^(3/2). если я введу число с 20 нулями, ждать вы будете до второго пришествия
0
Модератор
Эксперт по электронике
8908 / 6677 / 918
Регистрация: 14.02.2011
Сообщений: 23,523
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
Эксперт С++
4267 / 2241 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
09.07.2013, 19:59 18
Kukurudza, мы немного абстрагировались от совершенных чисел, речь о сумме делителей натурального числа. и Вы правильно поняли сложность алгоритма.

Но что касается совершенных чисел, то это понятно, что их по-другому проверяют
Получить совершенные числа
посты #3 и #4
0
1181 / 894 / 94
Регистрация: 03.08.2011
Сообщений: 2,461
09.07.2013, 20:02 19
Thinker, так скорей всего Ваш код и будет быстрее, так как операция деления довольно дорогая.
0
106 / 87 / 13
Регистрация: 29.08.2012
Сообщений: 539
09.07.2013, 20:04 20
Toshkarik на самом деле на сегодняшний момент операция деления такая же по стоимости как и умножение. как она реадизована я не в курсе в современных процессорах. я лично проверял на i5 процессоре.
0
09.07.2013, 20:04
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
09.07.2013, 20:04
Помогаю со студенческими работами здесь

Алгоритм выделения разрядов числа и проверки, есть ли среди них нечетная цифра
Задание. Дано трехзначное число. Составить алгоритм выделения его разрядов и проверки, есть ли...

Составить алгоритм проверки гипотезы Гольдбаха о представлении каждого чётного числа в виде суммы двух простых
Составить алгоритм проверки гипотезы Гольдбаха о представлении каждого чётного числа n(n&gt;2) в виде...

Дано четырехзначное число. Составить алгоритм выделения его разрядов и проверки, составляют ли цифры числа упорядоченную последовательность.
Дано четырехзначное число. Составить алгоритм выделения его разрядов и проверки,...

Написать код программы проверки целого числа на симметрию , проверки строки на симметрию символов
Код на C++ Помогите пожалуйста!

нахождение среднего арифметического всего массива и проверка на совершенность
Помогите пожалуйста с задачей: дан массив- 20 элементов, необходимо найти среднее арифметическое...

Алгоритм проверки
Всем доброго времени суток! Есть один код, это как бы шашки. Задача программы определить какие...


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

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru