Mod и остаток — не одно и то же
Приготовьтесь, вас ждёт крайне педантичная статья, которая вполне может спасти вас на собеседовании или сэкономить несколько часов при вылавливании бага в продакшне!
Я сейчас активно работаю над вторым сезоном «Руководства для самозванца» и пишу о шифре RSA для SSH, который, очевидно, является самым загружаемым фрагментом кода в истории IT.
Хочется полностью разобраться в этой истории. Кто придумал этот шифр, как он работает, почему работает и будет ли работать в будущем. Сейчас я раскопал одну чертовски интересную историю. Я не криптоманьяк и вижу, как других буквально засасывает в эту область. Но мне это тоже интересно, потому что повсюду есть маленькие норки, а меня как сороку привлекают блестящие штучки в глубоких норках. Я также очень хорош в метафорах.
В любом случае: на прошлой неделе я узнал что-то странное и хочу поделиться: оказывается, mod и остаток от деления — не одно и то же. Действительно забавно то, что некоторые читатели при этих словах выпрыгивают со своих кресел и орут: «А ведь именно это я всегда пытался сказать вам и всем остальным!»
Позовите ребят из секты «mod не остаток»! Это для вас.
Что такое mod?
Я должен был изучить это, как и в прошлый раз, когда всплыла такая тема. Это одна из тех вещей, которые ты знаешь, но не запоминаешь. Когда вы применяете mod, то делите одно число на другое и берёте остаток. Итак: 5 mod 2 будет 1, потому что 5/2=2 с остатком 1.
Термин mod означает операцию modulo, с модулем 2 в данном случае. Большинство языков программирования используют % для обозначения такой операции: 5 % 2 = 1 .
Вот где мы попадаем в странную серую область.
Математика циферблата
Помню, как учил это в школе, а потом забыл. Существует тип математики, называемый «модульной арифметикой», которая имеет дело с циклическими структурами. Самый простой способ представить это — циферблат с циклом 12. Для математика циферблат — это mod 12 . Если хотите понять, можно ли равномерно разделить 253 часа на дни, то можете применить операцию 253 mod 24 , результатом будет 13, поэтому ответ «нет»! Мы можем ответить «да» только если результат 0.
Другой вопрос, который вы можете задать: «Если я выеду в 6 вечера, сколько времени будет по приезду через 16 часов?». Это будет 6 + 16 mod 12 , то есть 10.
Криптографы любят mod , потому что при использовании с действительно большими числами можно создать нечто, известное как «односторонние функции». Это специальные функции, которые позволяют легко вычислить что-то в одном направлении, но не в обратном.
Если я скажу вам, что 9 является результатом возведения в квадрат, вы можете легко определить, что на входе было 3. Перед вами весь процесс от начала до конца. Если я скажу, что 9 является результатом mod 29 , то будет сложнее понять, что на входе.
Криптографам нравится эта идея, потому что они могут использовать деление с остатком с гигантскими простыми числами для генерации криптографических ключей. Это совсем другая история: если хотите прочитать об этом, то можете купить книгу или, ещё лучше, поддержать мои усилия написать её.
Впрочем, не будем отклоняться от темы.
Остатки и математика циферблата
Теперь переходим к сути: modulo и простой остаток одинаковы, когда числа положительны, но отличаются в случае отрицательных чисел.
Рассмотрим такую задачу:
const x = 19 % 12; console.log(x);Каково значение x ? Делим числа и получаем 7 как остаток от 12. Это верный ответ. Как насчет такого:
const y = 19 % -12; console.log(y);Используя обычную математику, мы можем умножить -12 на -1, что даёт 12, и у нас по-прежнему остаётся 7, поэтому наш ответ снова 7.
JavaScript с этим согласен:
C# тоже согласен:
Google согласен с первым утверждением, но не согласен со вторым:
Ruby согласен с Google:
Во имя Дейкстры, что здесь происходит?
Вращение часов назад
Чтобы ответить на вопрос, следует понять разницу между остатком и modulo. Программисты объединяют эти операции, но не должны этого делать, потому что они дают одинаковый результат только в случае, если делитель (в нашем случае 12) положителен. Вы можете легко отправить баги в продакшн, если делитель отрицательный.
Но почему существует разница? Рассмотрим положительный делитель 19 mod 12 на часах:
Конечный результат 7. Мы это знаем и мы можем доказать математически. Но что насчёт 19 mod -12 ? Здесь нужно использовать другие часы:
Модуль равен -12, и мы не можем игнорировать или изменить его, умножив на -1, поскольку модульная арифметика так не работает. Единственный способ правильно рассчитать результат — переставить метки на часах так, чтобы мы двигались от -12 или вращали часы против часовой стрелки, что даёт тот же результат.
Почему не начать метки с -1, двигаясь к -2, и т.д.? Потому что в таком случае мы будем двигаться назад и постоянно уменьшать результат, пока не достигнем -12, и в этот момент сделаем прыжок +12, а modulo так не работает.
Это известная вещь
Прежде чем назвать меня сумасшедшим и начать гуглить тему: это известный факт. На самом деле MDN (Mozilla Developer Network) даже дошла до того, чтобы назвать % операцией «остатка» (remainder), а не modulo:
Оператор remainder возвращает остаток от деления одного операнда на другой. Он всегда принимает знак делимого.
Вот что Эрик Липперт, один из богов C#, говорит о modulo в C#:
Однако это совсем не то, что оператор % реально делает в C#. Оператор % не является каноническим оператором modulus, это оператор остатка.
А как на вашем языке?
Ну и что?
Могу понять, если вы дочитали досюда, а теперь чешете голову и задаётесь вопросом, стоит ли беспокоиться. Думаю, что стоит по двум причинам:
- Я представляю, как этот вопрос займёт меня врасплох на собеседовании.
- Я представляю, как этот попадёт в продакшн, а разработчики будут несколько часов выяснять, почему математика не работает.
Теория чисел¶
Простым называется натуральное число, которое делится только на единицу и на себя. Единица при этом простым числом не считается. Составным числом называют непростое число, которое еще и не единица.
Примеры простых чисел: $2$, $3$, $5$, $179$, $10^9+7$, $10^9+9$.
Примеры составных чисел: $4$, $15$, $2^$.
Еще одно определение простого числа: $N$ — простое, если у $N$ ровно два делителя. Эти делители при этом равны $1$ и $N$.
Проверка на простоту за линию¶
С точки зрения программирования интересно научиться проверять, является ли число $N$ простым. Это очень легко сделать за $O(N)$ — нужно просто проверить, делится ли оно хотя бы на одно из чисел $2, 3, 4, \ldots, N-1$ . $N > 1$ является простым только в случае, если оно не делится на на одно из этих чисел.
def is_prime(n): if n == 1: return False for i in range(2, n): # начинаем с 2, так как на 1 все делится; n не включается if n % i == 0: return False return True for i in range(1, 10): print(i, is_prime(i))
(1, False) (2, True) (3, True) (4, False) (5, True) (6, False) (7, True) (8, False) (9, False)
Проверка на простоту за корень¶
Алгоритм можно ускорить с $O(N)$ до $O(\sqrt)$.
Пусть $N = a \times b$, причем $a \leq b$. Тогда заметим, что $a \leq \sqrt N \leq b$.
Иными словами, если число $N$ равно произведению двух других, то одно из них не больше корня из $N$, а другое не меньше корня из $N$.
Из этого следует, что если число $N$ не делится ни на одно из чисел $2, 3, 4, \ldots, \lfloor\sqrt\rfloor$, то оно не делится и ни на одно из чисел $\lceil\sqrt\rceil + 1, \ldots, N-2, N-1$, так как если есть делитель больше корня (не равный $N$), то есть делитель и меньше корня (не равный 1). Поэтому в цикле for достаточно проверять числа не до $N$, а до корня.
def is_prime(n): if n == 1: return False # Удобно вместо for i in range(2, n ** 0.5) писать так: i = 2 while i * i n: if n % i == 0: return False i += 1 return True for i in [1, 2, 3, 10, 11, 12, 10**9+6, 10**9+7]: print(i, is_prime(i))
(1, False) (2, True) (3, True) (10, False) (11, True) (12, False) (1000000006, False) (1000000007, True)
Разложение на простые множители¶
Любое натуральное число можно разложить на произведение простых, и с такой записью очень легко работать при решении задач. Разложение на простые множители еще называют факторизацией.
$$11 = 11 = 11^1$$$$100 = 2 \times 2 \times 5 \times 5 = 2^2 \times 5^2$$$$126 = 2 \times 3 \times 3 \times 7 = 2^1 \times 3^2 \times 7^1$$
Рассмотрим, например, такую задачу:
Условие: Нужно разбить $N$ людей на группы равного размера. Нам интересно, какие размеры это могут быть.
Решение: По сути нас просят найти число делителей $N$. Нужно посмотреть на разложение числа $N$ на простые множители, в общем виде оно выглядит так:
$$N= p_1^ \times p_2^ \times \ldots \times p_k^$$
Теперь подумаем над этим выражением с точки зрения комбинаторики. Чтобы «сгенерировать» какой-нибудь делитель, нужно подставить в степень $i$-го простого число от 0 до $a_i$ (то есть $a_i+1$ различное значение), и так для каждого. То есть делитель $N$ выглядит ровно так: $$M= p_1^ \times p_2^ \times \ldots \times p_k^, 0 \leq b_i \leq a_i$$ Значит, ответом будет произведение $(a_1+1) \times (a_2+1) \times \ldots \times (a_k + 1)$.
Алгоритм разложения на простые множители¶
Применяя алгоритм проверки числа на простоту, мы умеем легко находить минимальный простой делитель числа N. Ясно, что как только мы нашли простой делитель числа $N$, мы можем число $N$ на него поделить и продолжить искать новый минимальный простой делитель.
Будем перебирать простой делитель от $2$ до корня из $N$ (как и раньше), но в случае, если $N$ делится на этот делитель, будем просто на него делить. Причем, возможно, нам понадобится делить несколько раз ($N$ может делиться на большую степень этого простого делителя). Так мы будем набирать простые делители и остановимся в тот момент, когда $N$ стало либо $1$, либо простым (и мы остановились, так как дошли до корня из него). Во втором случае надо еще само $N$ добавить в ответ.
Напишем алгоритм факторизации:
def factorize(n): factors = [] i = 2 while i * i n: # перебираем простой делитель while n % i == 0: # пока N на него делится n //= i # делим N на этот делитель factors.append(i) i += 1 # возможно, в конце N стало большим простым числом, # у которого мы дошли до корня и поняли, что оно простое # его тоже нужно добавить в разложение if n > 1: factors.append(n) return factors for i in [1, 2, 3, 10, 11, 12, 10**9+6, 10**9+7]: print(i, '=', ' x '.join(str(x) for x in factorize(i)))
1 = 2 = 2 3 = 3 10 = 2 x 5 11 = 11 12 = 2 x 2 x 3 1000000006 = 2 x 500000003 1000000007 = 1000000007
Задание¶
За сколько работает этот алгоритм?
Решение¶
За те же самые $O(\sqrt)$. Итераций цикла while с перебором делителя будет не больше, чем $\sqrt$. Причем ровно $\sqrt$ операций будет только в том случае, если $N$ — простое.
А итераций деления $N$ на делители будет столько, сколько всего простых чисел в факторизации числа $N$. Понятно, что это не больше, чем $O(\log)$.
Задание¶
Докажите, что число $N$ имеет не больше, чем $O(\log)$ простых множителей в факторизации.
Разные свойства простых чисел*¶
Вообще, про простые числа известно много свойств, но почти все из них очень трудно доказать. Вот еще некоторые из них:
- Простых чисел, меньших $N$, примерно $\frac<\ln N>$.
- N-ое простое число равно примерно $N\ln N$.
- Простые числа распределены более-менее равномерно. Например, если вам нужно найти какое-то простое число в промежутке, то можно их просто перебрать и проверить — через несколько сотен какое-нибудь найдется.
- Для любого $N \ge 2$ на интервале $(N, 2N)$ всегда найдется простое число (Постулат Бертрана)
- Впрочем, существуют сколь угодно длинные отрезки, на которых простых чисел нет. Самый простой способ такой построить — это начать с $N! + 2$.
- Есть алгоритмы, проверяющие число на простоту намного быстрее, чем за корень.
- Максимальное число делителей равно примерно $O(\sqrt[3])$. Это не математический результат, а чисто эмпирический — не пишите его в асимптотиках.
- Максимальное число делителей у числа на отрезке $[1, 10^5]$ — 128
- Максимальное число делителей у числа на отрекзке $[1, 10^9]$ — 1344
- Максимальное число делителей у числа на отрезке $[1, 10^]$ — 103680
Решето Эратосфена¶
Часто нужно не проверять на простоту одно число, а найти все простые числа до $N$. В этом случае наивный алгоритм будет работать за $O(N\sqrt N)$, так как нужно проверить на простоту каждое число от 1 до $N$.
Но древний грек Эратосфен предложил делать так:
Запишем ряд чисел от 1 до $N$ и будем вычеркивать числа:
- делящиеся на 2, кроме самого числа 2
- затем деляющиеся на 3, кроме самого числа 3
- затем на 5, затем на 7, и так далее и все остальные простые до n. Таким образом, все незачеркнутые числа будут простыми — «решето» оставит только их.
Задание¶
Найдите этим способом на бумажке все простые числа до 50, потом проверьте с программой:
N = 50 prime = [1] * (N + 1) prime[0], prime[1] = 0, 0 for i in range(2, N + 1): # можно и до sqrt(N) if prime[i]: for j in range(2 * i, N + 1, i): # идем с шагом i, можно начиная с i * i prime[j] = 0 for i in range(1, N + 1): if prime[i]: print(i)
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47
У этого алгоритма можно сразу заметить несколько ускорений.
Во-первых, число $i$ имеет смысл перебирать только до корня из $N$, потому что при зачеркивании составных чисел, делящихся на простое $i > \sqrt N$, мы ничего не зачеркнем. Почему? Пусть существует составное $M \leq N$, которое делится на %i%, и мы его не зачеркнули. Но тогда $i > \sqrt N \geq \sqrt M$, а значит по ранее нами доказанному утверждению $M$ должно делиться и на простое число, которое меньше корня. Но это значит, что мы его уже вычеркнули.
Во-вторых, по этой же самое причине $j$ имеет смысл перебирать только начиная с $i^2$. Зачем вычеркивать $2i$, $3i$, $4i$, . $(i-1)i$, если они все уже вычеркнуты, так как мы уже вычеркивали всё, что делится на $2$, $3$, $4$, . $(i-1)$.
Асимптотика¶
Такой код будет работать за $O(N \log \log N)$ по причинам, которые мы пока не хотим объяснять формально.
Гармонический ряд¶
Научимся оценивать асимптотику величины $1 + \frac + \ldots + \frac$, которая нередко встречается в задачах, где фигурирует делимость.
Возьмем $N$ равное $2^i — 1$ и запишем нашу сумму следующим образом: $$\left(\frac\right) + \left(\frac + \frac\right) + \left(\frac + \ldots + \frac\right) + \ldots + \left(\frac> + \ldots + \frac\right)$$
Каждое из этих слагаемых имеет вид $$\frac + \ldots + \frac — 1> \le \frac + \ldots + \frac = 2^j \frac = 1$$
Таким образом, наша сумма не превосходит $1 + 1 + \ldots + 1 = i \le 2\log_2(2^i — 1)$. Тем самым, взяв любое $N$ и дополнив до степени двойки, мы получили асимптотику $O(\log N)$.
Оценку снизу можно получить аналогичным образом, оценив каждое такое слагаемое снизу значением $\frac$.
Попытка объяснения асимптотики** (для старших классов)¶
Мы знаем, что гармонический ряд $1 + \frac + \frac + \ldots + \frac$ это примерно $\log N$, а значит $$N + \frac + \frac + \ldots + \frac \sim N \log N$$
А что такое асимптотика решета Эратосфена? Мы как раз ровно $\frac
$ раз зачеркиваем числа делящиеся на простое число $p$. Если бы все числа были простыми, то мы бы как раз получили $N \log N$ из формули выше. Но у нас будут не все слагаемые оттуда, только с простым $p$, поэтому посмотрим чуть более точно.
Известно, что простых чисел до $N$ примерно $\frac<\log N>$, а значит допустим, что k-ое простое число примерно равно $k ln k$. Тогда
Но вообще-то решето можно сделать и линейным.
Задание¶
Решите 5 первых задач из этого контеста:
Линейное решето Эратосфена*¶
Наша цель — для каждого числа до $N$ посчитать его минимальный простой делитель. Будем хранить его в массиве min_d. Параллельно будем хранить и список всех найденных простых чисел primes — это ровно те числа $x$, у которых $min\_d[x] = x$.
Основное утверждение такое:
Пусть у числа $M$ минимальный делитель равен $a$. Тогда, если $M$ составное, мы хотим вычеркнуть его ровно один раз при обработке числа $\frac$.
Мы также перебираем число $i$ от $2$ до $N$. Если $min\_d[i]$ равно 0 (то есть мы не нашли ни один делитель у этого числа еще), значит оно простое — добавим в primes и сделаем $min\_d[i] = i$.
Далее мы хотим вычеркнуть все числа $i \times k$ такие, что $k$ — это минимальный простой делитель этого числа. Из этого следует, что необходимо и достаточно перебрать $k$ в массиве primes, и только до тех пор, пока $k < min\_d[i]$. Ну и перестать перебирать, если $i \times k >N$.
Алгоритм пометит все числа по одному разу, поэтому он корректен и работает за $O(N)$.
N = 30 primes = [] min_d = [0] * (N + 1) for i in range(2, N + 1): if min_d[i] == 0: min_d[i] = i primes.append(i) for p in primes: if p > min_d[i] or i * p > N: break min_d[i * p] = p print(i, min_d) print(min_d) print(primes)
2 [0, 0, 2, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] 3 [0, 0, 2, 3, 2, 0, 2, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] 4 [0, 0, 2, 3, 2, 0, 2, 0, 2, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] 5 [0, 0, 2, 3, 2, 5, 2, 0, 2, 3, 2, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0] 6 [0, 0, 2, 3, 2, 5, 2, 0, 2, 3, 2, 0, 2, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0] 7 [0, 0, 2, 3, 2, 5, 2, 7, 2, 3, 2, 0, 2, 0, 2, 3, 0, 0, 0, 0, 0, 3, 0, 0, 0, 5, 0, 0, 0, 0, 0] 8 [0, 0, 2, 3, 2, 5, 2, 7, 2, 3, 2, 0, 2, 0, 2, 3, 2, 0, 0, 0, 0, 3, 0, 0, 0, 5, 0, 0, 0, 0, 0] 9 [0, 0, 2, 3, 2, 5, 2, 7, 2, 3, 2, 0, 2, 0, 2, 3, 2, 0, 2, 0, 0, 3, 0, 0, 0, 5, 0, 3, 0, 0, 0] 10 [0, 0, 2, 3, 2, 5, 2, 7, 2, 3, 2, 0, 2, 0, 2, 3, 2, 0, 2, 0, 2, 3, 0, 0, 0, 5, 0, 3, 0, 0, 0] 11 [0, 0, 2, 3, 2, 5, 2, 7, 2, 3, 2, 11, 2, 0, 2, 3, 2, 0, 2, 0, 2, 3, 2, 0, 0, 5, 0, 3, 0, 0, 0] 12 [0, 0, 2, 3, 2, 5, 2, 7, 2, 3, 2, 11, 2, 0, 2, 3, 2, 0, 2, 0, 2, 3, 2, 0, 2, 5, 0, 3, 0, 0, 0] 13 [0, 0, 2, 3, 2, 5, 2, 7, 2, 3, 2, 11, 2, 13, 2, 3, 2, 0, 2, 0, 2, 3, 2, 0, 2, 5, 2, 3, 0, 0, 0] 14 [0, 0, 2, 3, 2, 5, 2, 7, 2, 3, 2, 11, 2, 13, 2, 3, 2, 0, 2, 0, 2, 3, 2, 0, 2, 5, 2, 3, 2, 0, 0] 15 [0, 0, 2, 3, 2, 5, 2, 7, 2, 3, 2, 11, 2, 13, 2, 3, 2, 0, 2, 0, 2, 3, 2, 0, 2, 5, 2, 3, 2, 0, 2] 16 [0, 0, 2, 3, 2, 5, 2, 7, 2, 3, 2, 11, 2, 13, 2, 3, 2, 0, 2, 0, 2, 3, 2, 0, 2, 5, 2, 3, 2, 0, 2] 17 [0, 0, 2, 3, 2, 5, 2, 7, 2, 3, 2, 11, 2, 13, 2, 3, 2, 17, 2, 0, 2, 3, 2, 0, 2, 5, 2, 3, 2, 0, 2] 18 [0, 0, 2, 3, 2, 5, 2, 7, 2, 3, 2, 11, 2, 13, 2, 3, 2, 17, 2, 0, 2, 3, 2, 0, 2, 5, 2, 3, 2, 0, 2] 19 [0, 0, 2, 3, 2, 5, 2, 7, 2, 3, 2, 11, 2, 13, 2, 3, 2, 17, 2, 19, 2, 3, 2, 0, 2, 5, 2, 3, 2, 0, 2] 20 [0, 0, 2, 3, 2, 5, 2, 7, 2, 3, 2, 11, 2, 13, 2, 3, 2, 17, 2, 19, 2, 3, 2, 0, 2, 5, 2, 3, 2, 0, 2] 21 [0, 0, 2, 3, 2, 5, 2, 7, 2, 3, 2, 11, 2, 13, 2, 3, 2, 17, 2, 19, 2, 3, 2, 0, 2, 5, 2, 3, 2, 0, 2] 22 [0, 0, 2, 3, 2, 5, 2, 7, 2, 3, 2, 11, 2, 13, 2, 3, 2, 17, 2, 19, 2, 3, 2, 0, 2, 5, 2, 3, 2, 0, 2] 23 [0, 0, 2, 3, 2, 5, 2, 7, 2, 3, 2, 11, 2, 13, 2, 3, 2, 17, 2, 19, 2, 3, 2, 23, 2, 5, 2, 3, 2, 0, 2] 24 [0, 0, 2, 3, 2, 5, 2, 7, 2, 3, 2, 11, 2, 13, 2, 3, 2, 17, 2, 19, 2, 3, 2, 23, 2, 5, 2, 3, 2, 0, 2] 25 [0, 0, 2, 3, 2, 5, 2, 7, 2, 3, 2, 11, 2, 13, 2, 3, 2, 17, 2, 19, 2, 3, 2, 23, 2, 5, 2, 3, 2, 0, 2] 26 [0, 0, 2, 3, 2, 5, 2, 7, 2, 3, 2, 11, 2, 13, 2, 3, 2, 17, 2, 19, 2, 3, 2, 23, 2, 5, 2, 3, 2, 0, 2] 27 [0, 0, 2, 3, 2, 5, 2, 7, 2, 3, 2, 11, 2, 13, 2, 3, 2, 17, 2, 19, 2, 3, 2, 23, 2, 5, 2, 3, 2, 0, 2] 28 [0, 0, 2, 3, 2, 5, 2, 7, 2, 3, 2, 11, 2, 13, 2, 3, 2, 17, 2, 19, 2, 3, 2, 23, 2, 5, 2, 3, 2, 0, 2] 29 [0, 0, 2, 3, 2, 5, 2, 7, 2, 3, 2, 11, 2, 13, 2, 3, 2, 17, 2, 19, 2, 3, 2, 23, 2, 5, 2, 3, 2, 29, 2] 30 [0, 0, 2, 3, 2, 5, 2, 7, 2, 3, 2, 11, 2, 13, 2, 3, 2, 17, 2, 19, 2, 3, 2, 23, 2, 5, 2, 3, 2, 29, 2] [0, 0, 2, 3, 2, 5, 2, 7, 2, 3, 2, 11, 2, 13, 2, 3, 2, 17, 2, 19, 2, 3, 2, 23, 2, 5, 2, 3, 2, 29, 2] [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Этот алгоритм работает асимптотически быстрее, чем обычное решето. Но на практике, если писать обычное решето Эратсфена с оптимизациями, то оно оказывается быстрее линейнего. Также линейное решето занимает гораздо больше памяти — ведь в обычном решете можно хранить просто $N$ бит, а здесь нам нужно $N$ чисел и еще массив primes.
Зато один из «побочных эффектов» алгоритма — он неявно вычисляет факторизацию всех чисел от $1$ до $N$. Ведь зная минимальный простой делитель любого числа от $1$ до $N$ можно легко поделить на это число, посмотреть на новый минимальный простой делитель и так далее.