Ну что ж, из уважения к Вашим сединам сыграю один раз по чужим правилам:).
Я писал о числах, влезающих в интеджер, т. е. до порядка 32 тысяч. В интервале 1..32000 лежит около 2500 простых. Таким образом, если оценивать сверху размером типа, при реализации решета вычеркнуть прийдётся где-то 29500 чисел.
Если, как я предложил, каждое нечётное делить на все простые, которые меньше квадратного корня из него, то делений прийдётся сделать не более чем 16000 умножить на количество простых, которые не превосходят корень из 32000 (это количество -- 41, но на самом деле результат будет меньше, это оценка сверху).
IDL> print, 1.6e4*41.
656000.
Теперь положим, что одно деление жрёт ресурса как 20 сложений, и поделим на заявленные четыре порядка::
IDL> print, 20.*1.6e4*41./1e4
1312.00
Итого:: если бы песня про четыре порядка была правильной, то решето в этом случае потребовало бы меньше, чем 1312 вычёркиваний.
Вердикт:: для типа интеджер четыре порядка -- гон, что и требовалось доказать. Гиннес прошу высылать в Мюнхен . С моей стороны спор окончен.