16 / 14 / 7
Регистрация: 04.11.2011
Сообщений: 137
|
||||||
1 | ||||||
Алгоритм проверки числа на "совершенность"09.07.2013, 17:31. Показов 8987. Ответов 42
Метки нет (Все метки)
Приветствую всех!
Прошу помочь со следующей задачей: "Натуральное число называется совершенным, если оно равно сумме всех своих делителей, за исключением себя самого. Число 6 – совершенное, так как 6 = 1+2+3. Число 8 – не совершенное, так как 8 ≠ 1+2+4.Дано натуральное число n. Получить все совершенные числа, меньшие n." Задачу я решил (код ниже), но работает программа слишком медленно. Пожалуйста помогите оптимизировать код, нужно чтобы программа требовала, как можно меньше памяти и работала быстрее.
Заранее всем благодарен))
0
|
09.07.2013, 17:31 | |
Ответы с готовыми решениями:
42
Проверка числа на совершенность Реализовать эффективный алгоритм проверки числа на простоту и подсчета количества делителей натурального числа Алгоритм проверки делимости числа на 7 Быстрый алгоритм проверки числа на простоту Нужен алгоритм проверки большого числа на простоту |
365 / 321 / 219
Регистрация: 21.02.2013
Сообщений: 756
|
||||||
09.07.2013, 18:38 | 2 | |||||
0
|
Модератор
8908 / 6677 / 918
Регистрация: 14.02.2011
Сообщений: 23,523
|
|||||||||||
09.07.2013, 18:54 | 3 | ||||||||||
вот это можешь заменить на
больше чем x/2 делителей нет (ну кроме x, а он по условию не проходит)
один два три можешь смело выбрасывать они простые значит не совершенные начинай с 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
|
09.07.2013, 19:35 | 6 |
правильно, но еще лучше до корня из числа
Быстрое нахождение количества делителей натурального числа посты #4 и #5
1
|
1181 / 894 / 94
Регистрация: 03.08.2011
Сообщений: 2,461
|
|
09.07.2013, 19:37 | 7 |
Thinker, почему же до корня? Ищем ведь не простые числа. К примеру возьмем 100. Корень == 10, но как же 20, 25 и 50?
0
|
1 / 1 / 0
Регистрация: 27.06.2013
Сообщений: 26
|
|
09.07.2013, 19:40 | 9 |
0
|
Модератор
8908 / 6677 / 918
Регистрация: 14.02.2011
Сообщений: 23,523
|
|
09.07.2013, 19:41 | 10 |
фиг вам
число 6 делители 1+2+3 =6 корень из числа 6 примерно 2,449 число 28 делители 1+2+4+7+14 =28 корень из числа 28 примерно 5.29 то что предложил это для простоты числа, если делителей меньше корня нет то и больше нет
0
|
1181 / 894 / 94
Регистрация: 03.08.2011
Сообщений: 2,461
|
||||||
09.07.2013, 19:46 | 12 | |||||
Thinker, это то понятно. Но тогда придется делать лишнюю операцию умножения, скорость если и будет чуть больше, но не намного. У меня с самого начала была идея что вроде такой:
0
|
1181 / 894 / 94
Регистрация: 03.08.2011
Сообщений: 2,461
|
|
09.07.2013, 19:48 | 14 |
ValeryS, Вы не поняли смысла. 6 / 2 == 3. И 2 и 3 являются делителями.
0
|
09.07.2013, 19:49 | 15 |
https://www.cyberforum.ru/post3547206.html
попробуйте сравнить по скорости с сумма делителей здесь есть небольшие хитрости и делители только нечетные проверяются, степени двойки выделяются с помощью битовых операций и т.д.
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 | ||||||||||
тут можно добавить еще одно условие и изменить направление
например для 100 50+25+20+10 вылетит можно до корня ну тогда цикл будет сложный что то типа
}
0
|
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 | |
09.07.2013, 20:04 | |
Помогаю со студенческими работами здесь
20
Алгоритм выделения разрядов числа и проверки, есть ли среди них нечетная цифра Составить алгоритм проверки гипотезы Гольдбаха о представлении каждого чётного числа в виде суммы двух простых Дано четырехзначное число. Составить алгоритм выделения его разрядов и проверки, составляют ли цифры числа упорядоченную последовательность. Написать код программы проверки целого числа на симметрию , проверки строки на симметрию символов нахождение среднего арифметического всего массива и проверка на совершенность Алгоритм проверки Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |