Казалось бы, решето Эратосфена - уже настолько известный алгоритм, что и говорить тут не о чем. Он упоминается в куче книг и сайтов, и почти везде (забавно, но есть некоторый процент расхождений) говорится, что он имеет асимптотику N log log N.

Так вот, вопрос: где-нибудь написано, откуда берётся эта асимптотика? Как ни удивительно, но я, несмотря на долгие поиски и на русском, и на английском языках, я нигде не нашёл доказательства. В статьях куча ссылок друг на друга, но что-то нигде дальше утверждения этой формулы ничего нет. Забавная ситуация, учитывая популярность и древность алгоритма 

Напомню, что требуется оценить такую вещь: для данного N сумма, по всем простым I от 1 до корня из N, величин N / I.

Заранее благодарен.

А вы знаете чему равна  сумма первых n  обратных значений   простых чисел?

1\2+1\3+1\5+1\7+1\11+1\13+1\17....

Эта сумма стремиться к лог лог(n)


Вообщем то отстальное тривиально.

Я знаю, что такой результат есть, но как его доказать? 

Я не знаю ни одного элементарного доказательства для этого факта. Но оно есть в интернете

Мне подсказали, что можно попробовать такой приём, как замена суммы на определённый интеграл (с теми же границами, что и у суммы; я это понял как приблизительную замену определённого интеграла формулой прямоугольников с шагом 1).
И похоже, у меня всё получилось:
берём сумму
СУММА 1/prime (по простым prime=2..N)
Заменяем её приближённо на сумму
СУММА 1 / (i ln i)  (по i=1.. N / ln N)
(здесь мы использовали основную теорему о простых, в прямую и обратную сторону)
А эту сумму заменяем на интеграл:
ИНТЕГРАЛ 1/(x ln x)  dx,   где x=1..N/lnN
Интегрируя, получаем  ln ln x, делаем подстановочку, получаем:
ln ln (N / lnN) - ln ln (1) = ln (ln N - ln ln N) - ln ln 1 = ln (ln N - ln ln N) - ln ln 1
Тут правда ln ln 1 нехорошая вещь, а взялось оно как 1-ое простое, поэтому заменим его на второе простое ln ln 2 (действительно, асимптотически это ничего не изменит), и дальше получаем:
ln (ln N - ln ln N) - ln ln 2 = O (ln ln N)
Ну вот вроде и всё.

Это сообщение отредактировал(а) maxdiver - 18.12.2008, 12:51

Cтранный переход

Ну количество простых, меньше либо равных N, оценивается согласно PNT - Prime Number Theorem (не знаю, как её по-русски) как N / lnN.
K-ое простое число приближённо можно оценить как K ln K (это можно получить из PNT; есть и более точная оценка для K-го простого числа: K ln K + K ln ln K - K < KthPrime < K ln K + K ln ln K, но мы отбрасываем члены меньшего порядка).

Вот эти два выражения и подставляем в сумму.