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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Массивы и перестановка http://www.cyberforum.ru/cpp-beginners/thread920370.html
Помогите пожалуйста с задачей. Дано 2 массива, заполненных случайными числами, размером от 10-20 (рандом). Найти в первом массиве максимальное число и все числа, находящиеся до него записать в 3ий...
C++ Создайте класс на основе данной программы Создайте класс на основе данной программы #include <iostream> using namespace std; int main ( ) { const int n=10; int* ap; for(int j=0;j<n;j++) *(ap+j)=new int; http://www.cyberforum.ru/cpp-beginners/thread920338.html
Как определить в каком файле .lib реализована функция? C++
Есть один проект. В нем файл .h с прототипами функций и множество .lib-ов, с их реализациями. Я данные функции пытаюсь использовать в другом проекте, но при попытки построить проект VS2010 выдает...
Как получить int представление char (русские символ cp1251)? C++
Как получить int представление char (русские символ cp1251)?
C++ решении задачи (по Липпману) http://www.cyberforum.ru/cpp-beginners/thread920326.html
Занимаюсь по книги Стенли Липпмана "C++ Primer" (Язык программирования С++. Вводный курс). Возникла проблема с решением задачи.Текст - прочитайте некоторый текст, сохраняя каждое введенное слово как...
C++ Кошки Здравствуйте! Как в этом коде сделать так чтобы если кошке менее 2 лет, то цена кошки = 0$; Заранее спасибо!!! И еще как можно это часть кода: оптимизировать. Cat Mumu(140); ... подробнее

Показать сообщение отдельно
Naudiz
14 / 12 / 1
Регистрация: 04.11.2011
Сообщений: 137
10.07.2013, 09:36  [ТС]
ValeryS, спасибо за замечания)) Сразу как-то и не подумал над х/2.
Чуть-чуть причесал код:
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
 
bool perfect(unsigned int x)
{
   unsigned int sum=0;
   for (int i=1; i<=x/2; i++)
      if (x%i==0) sum+=i;
   return x==sum;
}
 
int main()
{
   unsigned int x;
   std::cin >> x;
   for (unsigned int i=4; i<=x; i++)
      if (perfect(i)) std::cout << i << std::endl;
   return 0;
}

Kukurudza, благодарю за вики, появились кое какие мысли) Использование последовательности чисел Мерсенне способ весьма годный на практике, но когда речь идёт об алгоритмизации думаю не совсем уместен.

Цитата Сообщение от Kukurudza Посмотреть сообщение
реализованный алгоритм имеет нотацию O(n*n)
Это оценка скорости выполнения или количества операций алгоритма? Можно подробнее?

Thinker, Ваш алгоритм нахождения делителей числа действительно очень быстро работает. Еще не разобрался как он работает...

Вообщем по алгоритму проверки числа на совершенность пока идей больше нет, а вот как сократить количество итераций проверки самих чисел меньше заданного n (по условию) есть. Заинтересовало сл. св-во совершенных чисел в вики:
"Все чётные совершенные числа в двоичной записи содержат сначала p единиц, за которыми следует p—1 нулей (следствие из их общего представления)."

Таким образом можно было бы проверять все числа от 4 до n сначала на удовлетворение этому условию (операция, как я полагаю, менее затратная, если не ошибаюсь) и только проходящие по нему проверять на совершенность.
0
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru