|
Снова про простые числа
(Время: 1 сек. Память: 16 Мб Сложность: 27%)
Покажем, что проверить число x на простоту можно за время O(√x). Действительно, пусть x – составное, то есть у него есть хотя бы один делитель. Покажем, тогда, что у x есть делитель, не превосходящий √x.
Пусть x = a•b. Если a ≤ √x, то требуемый делитель найден. Иначе (a > √x), рассмотрим b = x/a ≤ x/√x = √x.
Таким образом, для проверки простоты числа за время O(√x) необходимо перебрать все числа от 2 до √x. Если хотя бы для одного i (2 ≤ i ≤ √x) i делит x, то число x не простое, иначе – простое.
Тогда возможно реализовать некую процедуру isPrime(x), которая возвращает true, если число x простое, и false в противном случае. Теперь воспользуемся тем, что |b-a| ≤ 1000. Из этого следует, что мы можем найти все простые числа в этом диапазоне за время O(|b-a|•√b). Найдя все числа (а их не более 1000), перебираем их и находим простое число с максимальной суммой цифр. Заметим, что хранить все простые числа от a до b нет необходимости, т.к. найдя очередное простое число, мы можем сравнить его сумму цифр с текущим максимумом.
Разбор: Александр Торопов.
| |
