Почему Сито Эратосфена более эффективно, чем простой «тупой» алгоритм?

Если вам нужно сгенерировать простые числа от 1 до N, "тупой" «способ сделать это - перебрать все числа от 2 до N и проверить, делятся ли числа на какое-либо найденное простое число, которое меньше квадратного корня из рассматриваемого числа.

Как я вижу оно, сито Эратосфена, делает то же самое, за исключением другого случая - когда оно находит простое N, оно отмечает все числа, кратные N.

Но отметите ли вы X, когда найдете N, или вы проверите если X делится на N, фундаментальная сложность, большой O остается неизменной. Вы по-прежнему выполняете одну операцию с постоянным временем для пары число-простое число. Фактически, глупый алгоритм прерывается, как только находит простое число, но сито Эратосфена помечает каждое число несколько раз - один раз для каждого простого числа, которое делится на. Это как минимум в два раза больше операций для каждого числа, кроме простых.

Я что-то не понимаю?