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

Question

[Homemade]

Задача
Моё решение
Например при d = 3 решение автора даёт 55 а у меня 28. Мне кажется, что я не совсем точно понял задачу. Помогите пожалуйста.

Answer 1

[Wataru]

28 тут не подходит, потому что надо что бы у числа было хотя бы 4 делителя и все делители отличались хотя бы на d.

У 28 шесть делителей (1, 2, 4, 7, 14, 28). Среди них есть делители 1 и 2, которые отличаются меньше чем на d=3.

Comments

[Homemade]

Ааа, дошло теперь. Я думал только эти 4 должны отличаться на d.
Спасибо Вам большое.

Answer 2

[Alexandroppolus]

В твоем решении x2 и x3 должны быть простыми числами, причем x2 >= 1+d, x3 >= x2+d.

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

Comments

[Homemade]

Благодарю за помощь!