Пожалуйста, прочтите новое правило об ограничении использования AI-инструментов. ×

Блог пользователя Creed

Решето Эратосфена за О(N)
Автор Creed, 13 лет назад, По-русски

Помогите, пожалуйста, с применением данной (в конце станицы) идеи. В частности интересует задание начальных данных для динамики.

И там есть один момент, когда рассматриваются 2 случая:

p[i] = 0 - тут все понятно =)

p[i] != 0 - не понятно когда оно вообще будет не равно 0

Если кто может помогите. Заранее спасибо

  • Проголосовать: нравится
  • -5
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
Каждое составное число можно представить в виде j=x*i, где x - наименьший простой делитель, а i - все остальное. Легко заметить, что x не должен превышать наименьший простой делитель и наоборот, если x не превышает его, то разложение - искомое. Для всех таких i мы перебираем все такие x и p[j] становится равным не 0, а очень даже x. Надеюсь, стало понятнее.
→ Ответить