Complexity: $O(n*\log{\log{n}})$

Задача: вычислить все простые числа от 1 до n;

Классическая реализация

Идея:

1. Выписать все числа от 2 до n;
2. Идём с самого начала: находим первое не зачёркнутое число x, оно 100% простое
3. Его добавляем в список primes;
4. Вычеркиваем всех ему кратных: 2x, 3x, 4x, …, kx (kx ≤ n)
5. Повторяем шаг №2 по циклу, пока не дойдём до n.

Улучшенный алгоритм

Идея:

1. Выписать все числа от 2 до n;
2. Идём с самого начала: находим первое не зачёркнутое число x, оно 100% простое
3. Его добавляем в список primes;
4. Вычеркиваем всех ему кратных, начиная с $x^2$: x*x, (x+1)*x, (x+2)*x, …, kx (kx ≤ n)
5. Повторяем шаг №2 по циклу, пока x$^2$ не станет больше n.

Док-во (почему можем начинать с $x^2$ на примере числа 11): зачёркнуты будут 211, 311, 411, 511, …, 1111, 1211, … Однако 211, 311, …, 10*11 уже вычеркнуты ранее, а это значит, что их рассматривать нет смысла.