Решето Эратосфена за O(n). Доказательство

for (i=2; i<=n; ++i) {
	if (lp[i]==0)
		pr[++np] = lp[i] = i;
	m = min(lp[i], n/i), d=0;
	for (k=0; k<np && pr[k+1]<=m; ++k)
		d = max(d, pr[k+1]-pr[k]);
	for (j=1; j<=d; ++j)
		a[j] = a[j-1]+i;
	pi=0;
	for (j=1; j<=k; ++j)
		pi += a[pr[j]-pr[j-1]], lp[pi] = pr[j];
}

От n/i можно избавиться, но тогда код станет сложнее.

Решето Эратосфена за O(n). Доказательство

Все i(pr[j]-pr[j-1]) мы предпосдчитали заранее в отдельный массив и заново умножать не надо, только складывать. Всего O(k) сложений, но так как (pr[j]-pr[j-1]) = O( k^(2/3)*log(k) ), то умножений в предподсчёте гораздо меньше.

Решето Эратосфена за O(n). Доказательство

Потому что смысл предподсчёта — посчитать i*j только для j до k^(2/3)*log(k), так как pr[k] = O(k*log(k)), а разности между соседними простыми — O(pr[k]^(2/3)). А потом основной цикл — предыдущее складываем с предподсчитанным.

Решето Эратосфена за O(n). Доказательство

Точнее O(k^(2/3)*log(k)*log(n)) у предпосчёта против O(k*log(n))
k — количество простых в цикле для данного i.
Предподсчёт тоже будем не в лоб умножать, а складывать.

Решето Эратосфена за O(n). Доказательство

Ну будет O(k^(2/3)*log(k)*log(log(k))), это асимптотически меньше чем O(k*log(k))

Решето Эратосфена за O(n). Доказательство

Я же зафиксировал i, значит для разных i считается независимо.
Так как (pr[k]-pr[k-1]) = O(pr[k] ^ (2/3)) асимптотически мало, мы можем предпосчитать все нужные произведения (pr[k]-pr[k-1])*i и это будет асимптотически меньше чем последующие сложения pr[k]*i = pr[k-1]*i + (pr[k]-pr[k-1])*i.

Решето Эратосфена за O(n). Доказательство

От log(log(n)) легко избавиться, если заметить, что мы вычисляем p*i, для фиксированного i, а p бежит по простым. Пользуясь тем, что (pr[k]-pr[k-1]) = O(pr[k] ^ (2/3)), можно предпосчитать q*i для нужных q, а потом умножение свести к сложению предыдущего с предпосчитанным.

Решето Эратосфена за O(n). Доказательство

Есть решето Аткина с временем работы Θ( n / log(log(n)) ) — статья
Там нет умножений чисел размера O( log(n) ), только сложения-вычитания и прочие линейные операции, т.е. битовая сложность Θ( n * log(n) / log(log(n)) )
При сложности умножения Θ(n * log(n)) у вас битовая сложность Θ(n * log n * log log n), такая же как и у обычного решета Эратосфена.
Т.е. «сэкономиленные» log(log(n)) вы на самом деле спрятали в сложность умножения.

Решето Эратосфена за O(n). Доказательство

У вас n — это граница до которой ищутся простые числа, зачем называть этой буквой ещё и её длину?

Решето Эратосфена за O(n). Доказательство

за n надо брать не границу до которой ищутся простые числа, а ее длину

А почему не длину этой длины, степенные башенки должны быть выше!
Если серьёзно, то длина это как раз граница до которой ищутся простые числа — n. Или КМП у вас работает за 2^n, а числа перемножаются за n*2^n?

Решето Эратосфена за O(n). Доказательство

А в какой вычислительной модели оценка O(N)?

Тут есть Θ(N) умножений двух чисел длины log(N), то есть Ω(N * log(N)) битовых операций.

Отсеиваем простые из миллиарда чисел быстрее, чем в Википедии

В 3 раза, (2/1)(3/2) = 3.

Если брать простые числа, которые взаимно просты с 2, 3, 5, 7 — Wheel factorization, то скорость возрастёт примерно в (2/1)(3/2)(5/4)(7/6) = 210/48 = 4.375 раза. Для миллиарда колесо делать больше невыгодно.

Отсеиваем простые из миллиарда чисел быстрее, чем в Википедии

www.spoj.com/problems/PRIMES2 — как раз задачка на поиск простых до миллиарда. Самое быстрое решение просеивает за 0.21 секунды на Intel Xeon E3-1220 v5. Алгоритм — segmented sieve of Eratosthenes with wheel factorization modulo 210

Формальная логика “request-response” в изучении английского: преимущества программистов

Это называется "short-circuit evaluation": можно отбросить часть логического выражения, когда она не влияет на результат.

Формальная логика “request-response” в изучении английского: преимущества программистов

Попробуйте приготовить и чай, и кофе. И пусть только попробует не выпить.

Не выпить чай или кофе?

Как волонтёры со всего мира создают прямой эфир ICPC-2019

А ещё приглашаю посмотреть трансляцию мероприятия (4-го апреля в 12:00 по московскому времени)

Здесь написано, что начало в 11, надо полагать по португальскому времени, UTC+1. У Москвы UTC+3, начало в 13. Или трансляция начнётся за час до начала мероприятия?

На Хабре открылся новостной раздел. Раскладываем всё по полкам

Ну так как бы этот блок как раз для новостей, зачем называть его new? Ваш кэп.

На Хабре открылся новостной раздел. Раскладываем всё по полкам

Это опечатка в разметке сайта и имелся в виду .news-block?
Или следующие новые блоки будут .newest-block, .super-new-block, ...

Новый мировой рекорд по вычислению числа пи: 31,4 трлн знаков

Ещё в 80-е годы сами братья Чудновские с его помощью рассчитали более триллиона знаков после запятой.

Чудновские были первыми, кто вычислил миллиард знаков. Полная хронология рекордов

Законопроект о борьбе с фейковой информацией принят в третьем чтении

Гораздо хуже, что закон даёт гибкость трактовать любую информацию как «фейк».