Задать вопрос
@Homemade

Почему моё решение данной задачи неправильное?

Задача
Моё решение
Например при d = 3 решение автора даёт 55 а у меня 28. Мне кажется, что я не совсем точно понял задачу. Помогите пожалуйста.
  • Вопрос задан
  • 306 просмотров
Подписаться 1 Простой Комментировать
Решения вопроса 2
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
28 тут не подходит, потому что надо что бы у числа было хотя бы 4 делителя и все делители отличались хотя бы на d.

У 28 шесть делителей (1, 2, 4, 7, 14, 28). Среди них есть делители 1 и 2, которые отличаются меньше чем на d=3.
Ответ написан
Alexandroppolus
@Alexandroppolus
кодир
В твоем решении x2 и x3 должны быть простыми числами, причем x2 >= 1+d, x3 >= x2+d.

Ну и весь прикол задачи - найти два таких простых числа. Скорее всего, надо предварительно построить таблицу с набором простых чисел. Это либо отсортированный массив оных, где можно искать двоичным поиском, либо массив, где a[i] = (минимальное простое, большее или равное i), с поиском за O(1). В любом случае, максимальное простое число, которое тебе вообще может понадобится, не больше чем 20200, так что много байтов это дело не займет. Ну и само собой, для создания подобного словаря можно воспользоваться решетом Эратосфена или чем-то подобным.
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Похожие вопросы