Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.50/8: Рейтинг темы: голосов - 8, средняя оценка - 4.50
0 / 0 / 0
Регистрация: 06.10.2022
Сообщений: 13

Найти все совершенные числа из диапазона от 1 до 1000

18.11.2022, 09:30. Показов 1861. Ответов 4
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Целое число называется совершенным, если сумма его делителей,
включая 1 (но не самое число) , равное этому числу. Например, число 6 = 1+2+3 есть
совершенным. Напишите программу perfect, которая определяет, является ли число совершенным.
Используйте эту функцию в программе, которая находит и печатает все совершенные числа из
диапазона от 1 до 1000
0
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
18.11.2022, 09:30
Ответы с готовыми решениями:

Найти все совершенные числа, меньшие 1000
Найти все совершенные числа, меньшие 1000. Число называется совершенным, если оно равно сумме всех своих делителей за исключением самого...

Найти все совершенные числа в пределе 1000
Найти все совершенные числа в пределе 1000.(на QBasic ., c помощью циклических алгоритмов )

Найти все совершенные числа из заданного диапазона
1)Найти все совершенные числа из диапозона.Если таких чисел нет,выдать соответствующее сообщение. Добавлено через 25 минут надеюсь...

4
Супер-модератор
Эксперт функциональных языков программированияЭксперт Python
 Аватар для Catstail
38161 / 21096 / 4306
Регистрация: 12.02.2012
Сообщений: 34,683
Записей в блоге: 14
18.11.2022, 12:14
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
#include <iostream>
 
using namespace std;
 
int isPerfect(int n)
{
    int r=1, i,k;
    i=2;
    while (i*i<=n)
    {
         if (n%i==0)
         {
            r+=i;
            k=n/i; 
            if (k != i) r+=k;
         }
         i++;
    }
    return (r==n);
}
 
int main()
{
    for (int i=2; i<=1000; i++)
         if (isPerfect(i)) printf("%d\n",i);
 
    return 0;
}
0
Вездепух
Эксперт CЭксперт С++
 Аватар для TheCalligrapher
12928 / 6796 / 1819
Регистрация: 18.10.2014
Сообщений: 17,193
18.11.2022, 21:12
Пользуясь результатами из Найти натуральное число от 1 до 10000 с максимальной суммой делителей

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <iostream>
 
unsigned get_sum_divisors(unsigned v)
{
  const unsigned MAX_MEMO = 1000;
  static unsigned memo_sum[MAX_MEMO + 1] = { 0, 1 };
  if (v <= MAX_MEMO && memo_sum[v] != 0)
    return memo_sum[v];
 
  unsigned d;
  for (d = 2; d * d <= v; ++d)
    if (v % d == 0)
      break;
 
  unsigned sum_v;
 
  if (d * d > v)
    // `v` простое число
    sum_v = 1 + v;
  else
  { // `d` - простое число
    unsigned sum_d = 1;
 
    unsigned r = v;
    for (unsigned dp = d; r % d == 0; r /= d, dp *= d)
    {
      sum_d += dp;
      if (dp <= MAX_MEMO)
        memo_sum[dp] = sum_d;
    }
 
    unsigned sum_r = get_sum_divisors(r);
    sum_v = sum_d * sum_r;
  }
 
  if (v <= MAX_MEMO)
    memo_sum[v] = sum_v;
 
  return sum_v;
}
 
bool is_perfect(unsigned v)
{
  return get_sum_divisors(v) == v + v;
}
 
int main() 
{
  for (unsigned i = 1; i <= 10000; ++i)
    if (is_perfect(i))
      std::cout << i << " ";
  
  std::cout << std::endl;
}
1
Вездепух
Эксперт CЭксперт С++
 Аватар для TheCalligrapher
12928 / 6796 / 1819
Регистрация: 18.10.2014
Сообщений: 17,193
19.11.2022, 10:32
На самом деле ключевой момент здесь - именно нахождение суммы делителей через факторизацию. А мемоизация дает непринципиальное ускорение. То есть можно реализовать все то же самое без мемоизации вообще

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
unsigned get_sum_divisors(unsigned v)
{
  unsigned sum_v = 1;
 
  for (unsigned d = 2; d * d <= v; ++d)
    if (v % d == 0)
    {
      unsigned sum_d = 1;
      for (unsigned dp = d; v % d == 0; v /= d, dp *= d)
        sum_d += dp;
 
      sum_v *= sum_d;
    }
 
  if (v > 1)
    sum_v *= v + 1;
 
  return sum_v;
}
 
bool is_perfect(unsigned v)
{
  return get_sum_divisors(v) == v + v;
}
На проверку всех чисел до 33550336 включительно

C++
1
2
3
for (unsigned i = 2; i <= 33550336; ++i)
  if (is_perfect(i)) 
    std::cout << i << std::endl;
этот вариант тратит примерно в 3.5 раза меньше времени, чем лобовая реализация предложенная Catstail.
1
Вездепух
Эксперт CЭксперт С++
 Аватар для TheCalligrapher
12928 / 6796 / 1819
Регистрация: 18.10.2014
Сообщений: 17,193
27.03.2024, 06:24
Возвращаясь к напечатанному:

Пользуясь привнесенной в обсуждение здесь теоремой Евклида-Эйлера можно предложить следующий, существенно более эффективный способ проверки числа на совершенство

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
bool is_perfect(unsigned long long v)
{
  unsigned p;
  for (p = 0; v % 2 == 0; v /= 2, ++p);
 
  if (p == 0)
    return false;
 
  unsigned long long mp = (1ull << (p + 1)) - 1;
  if (mp != v)
    return false;
 
  for (unsigned long long d = 3; d * d <= mp; d += 2)
    if (mp % d == 0)
      return false;
 
  return true;
}
Скорее всего нужно еще добавить сюда раннюю проверку на простоту числа p + 1. Так как p + 1 - число совсем маленькое (намного меньше, чем mp), предварительная проверка его на простоту с отсечением составных значений может послужить оптимизацией.

Разумеется, как настоящие математики, все мы должны относится к таким решениям скептически, ибо теорема Евклида-Эйлера позволяет производить проверку на совершенство лишь для четных чисел. Нечетные совершенные числа пока науке не известны, но и доказать невозможность их существования тоже пока никому не удалось. Поэтому надежды терять не стоит. (Где ж ты моё нечётное совершенство?)
1
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
27.03.2024, 06:24
Помогаю со студенческими работами здесь

Найдите все совершенные числа, меньшие 1000
Всем привет, помогите пожалуйста решить данную задачу.. заранее спасибо Натуральное число n называется совершенным, если сумма всех...

Вывести все совершенные числа из диапазона от 1 до n
Натуральное число назовем &quot;совершенным&quot;, если сумма его всевозможных делителей ( кроме самого числа) равна этому числу. Например,...

Найдите все совершенные числа из диапазона [a, b]
Найдите все совершенные числа из диапазона . (Совершенными называются числа, равные сумме своих делите- лей, без самого числа....

Найдите все совершенные числа от 1 до 1000 и выведите их на экран
Число совершенно,если она равна сумме всех своих делителей кроме самого себя.Пример :6=1+2+3 найдите все совершенные числа от 1 до 1000 и...

Найдите все совершенные числа от 1 до 1000 и выведите их на экран
Число совершенно,если она равна сумме всех своих делителей кроме самого себя.Пример:6=1+2+3 найдите все совершенные числа от 1 до 1000 и...


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

Или воспользуйтесь поиском по форуму:
5
Ответ Создать тему
Новые блоги и статьи
Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка.
Programma_Boinc 23.12.2025
Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Рецензия / Мнение/ Перевод https:/ / **********/ gallery/ thinkpad-x220-tablet-porn-gzoEAjs . . .
PhpStorm 2025.3: WSL Terminal всегда стартует в ~
and_y87 14.12.2025
PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .
Как объединить две одинаковые БД Access с разными данными
VikBal 11.12.2025
Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
Новый ноутбук
volvo 07.12.2025
Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro
Музыка, написанная Искусственным Интеллектом
volvo 04.12.2025
Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
От async/await к виртуальным потокам в Python
IndentationError 23.11.2025
Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов
Argus19 22.11.2025
Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .
Сколько Государство потратило денег на меня, обеспечивая инсулином.
Programma_Boinc 20.11.2025
Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .
Ломающие изменения в C#.NStar Alpha
Etyuhibosecyu 20.11.2025
Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .
Мысли в слух
kumehtar 18.11.2025
Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru