Любопытнее

Curiouser and curiouser
Alice in W.

Живешь себе, никого не трогаешь. А тебе говорят, что Эратосфена можно делать за линию. А ты не веришь, жил себе, никого не трогал. Не веришь, но любопытно. Как же так, ведь ты никого не трогал?! А тебе дают ссылку на статью 1978 года, блин 33 года назад. Как же ты вообще жил..?

И в самом деле, все оказывается тривиально. Так же тривиально, как Эратосфен с непонятным логарифмом. Даже до некоторого момента времени, Эратосфен казался медленнее чем тривиальное деление. И жили же тогда люди. А потом оказывается, что что-то непонятное быстрее и почему-то является log log n. Непонятно, но верим.

А тут линия, и на второй день становится все понятно, честная линия. Становится только не понятно, как же ты сам до этого не дошел? Видимо, никого не трогал.

Все любопытнее...

ЗЫ. David Gries, Jayadev Misra. A Linear Sieve Algorithm for Finding Prime Numbers [1978]