ДляПри выбранном <math>n \in \mathbb{N}</math> для каждого простого <math>p \in \mathbb{P}\colon p \le n</math> будет выполняться внутренний цикл, который совершит <math>\frac{n}{p}</math> действий. Следовательно, нужно оценить следующую величину:
<math> \sum^{}_\limits_{p\in \le n,mathbb{P}\colon p \subsetle primen} {\frac{n}{p}} </math> = <math> n*\cdot\sum^{}_\limits_{p\in \le n,mathbb{P}\colon p \subsetle primen} {\frac{1}{p}} </math>
Так как количество [[простое число|простых чисел]], меньшеменьших либо равных <math>n</math>, [[Теорема_о_распределении_простых_чисел|оценивается]] как <math>\frac{n}{\ln n}</math>, и, как следствие, <math>k</math>-е простое число примерно равно <math>k\ln k</math>, то сумму можно преобразовать:
Здесь из суммы выделено первоеслагаемое простоедля числопервого простого числа, чтобы избежать деления на нуль. Теперь следует оценить эту сумму интегралом:
