В комментариях к одному из прошлых постов о решете Эратосфена был упомянут этот короткий алгоритм из Википедии:
Алгоритм 1:
1: для i := 2, 3, 4, ..., до n:
2: если lp[i] = 0:
3: lp[i] := i
4: pr[] += {i}
5: для p из pr пока p ≤ lp[i] и p*i ≤ n:
6: lp[p*i] := p
Результат:
lp - минимальный простой делитель для кажого числа до n
pr - список всех простых до n.
Алгоритм простой, но не всем он показался очевидным. Главная же проблема в том, что на Википедии нет доказательства, а ссылка на первоисточник (pdf) содержит довольно сильно отличающийся от приведенного выше алгоритм.
В этом посте я попытаюсь, надеюсь, доступно доказать, что этот алгоритм не только работает, но и делает это за линейную сложность.
Читать полностью »