Для заданного числа N выведите все простые числа от 0 до N.
Примеры:
Ввод: 5
Вывод: 2, 3, 5
Ввод: 20
Вывод: 2, 3, 5, 7, 11, 13, 17, 19
Подход BruteForce: выполните итерацию от 2 до N и проверьте, является ли оно простым или нет. Если это простое число,
выведите число.
Примечание. 0 и 1 не являются простыми числами. 2 — наименьшее простое число.
Нажмите здесь, чтобы увидеть код:
Временная сложность: O(N²)
Пространственная сложность: O(1)
Эффективный подход: мы можем уменьшить временную сложность с O(N²) до O(N^3/2), уменьшив пространство поиска с [2, N) до [2, sqrt(N)] в функции isPrime, потому что один из множителей N должен быть равен или
меньше квадратного корня из N.
Оптимальный подход: использование решета Эратосфена
Создайте логический массив prime[0….N] и инициализируйте все записи как истинные.
Значение в Prime[i] будет ложным, если i не простое число, иначе оно будет истинным.
Выполнить цикл for от 2 до ceil значение квадратного корня из N.
Во время итерации, если Prime[p] истинно, то оно не изменяется ранее.
Изменяет все кратные p больше или равные возвести его в квадрат до N.
Числа, кратные p и меньшие p^2, уже помечены как ложные.
Теперь пройдемся по массиву от 2 до N и проверим, является ли простым[p ] истинно или ложно.
Если prime[p] истинно, то это простое число.
Если prime[p] ложно, то это не простое число.
Нажмите здесь, чтобы получить код:
Временная сложность: O(N*log(log(N)))
Пространственная сложность: O(N)
