Решето: наименьший простой делитель
Теория чисел
Средняя
Дано число n. Верните массив spf длины n+1, где spf[i] - наименьший простой делитель числа i (spf[0] и spf[1] можно оставить равными 0 и 1 соответственно - для них наименьший простой делитель не определён).
Постройте spf решетом за O(n log log n), а не проверкой делителей для каждого числа отдельно.
Сигнатура функции
smallest_prime_factors(n: int) -> list[int]
Примеры
| Вход | Ожидаемый результат |
|---|
| [10] | [0, 1, 2, 3, 2, 5, 2, 7, 2, 3, 2] |
| [1] | [0, 1] |
1решили
1пытались
100%успешность
Войдите, чтобы решить →