2021-11-09
46
Реализация
| const int n = 1e6; vector<int> lp(n + 1, 0); vector<int> pr; for (int k = 2; k <= n; k++) { if (pr[k] == 0) { lp[k] = k; pr.push_back(k); } for (int & x: pr) { if (x > lp[k] || x * lp[k] > n) break; lp[k * x] = x; } } |
Докажем корректность алгоритма, т. е. что он корректно расставляет все значения lp[], причём каждое из них будет установлено ровно один раз. Отсюда будет следовать, что алгоритм работает за линейное время — поскольку все остальные действия алгоритма, очевидно, работают за O (n).
Для этого заметим, что у любого числа i единственно представление такого вида:
i = lp[i] * x,
где lp[i] — минимальный простой делитель числа i, а число x не имеет делителей, меньших lp[i], т. е.:
lp[i] <= lp[x].
Теперь сравним это с тем, что делает наш алгоритм — он фактически для каждого x перебирает все простые, на которые его можно домножить, т. е. простые до lp[x] включительно, чтобы получить числа в указанном выше представлении. Следовательно, алгоритм действительно пройдёт по каждому составному числу ровно один раз, поставив у него правильное значение lp[]. Это означает корректность алгоритма и то, что он работает за линейное время.
Хотя асимптотика O (n) лучше асимптотики O (n log log n) классического решета Эратосфена, разница между ними невелика. На практике это означает лишь двукратную разницу в скорости, а оптимизированные варианты решета Эратосфена и вовсе не проигрывают приведённому здесь алгоритму. Учитывая затраты памяти, которые требует этот алгоритм — массив чисел lp[] длины n и массив всех простых pr[] длины примерно n / ln n — этот алгоритм кажется уступающим классическому решету по всем статьям. Однако спасает его то, что массив lp[], вычисляемый этим алгоритмом, позволяет искать факторизацию любого числа в отрезке [2; n] за время порядка размера этой факторизации.
