A5. Найти всех простых
Задание
Дано число 𝘕. Требуется найти все такие числа из отрезка [1;𝘕] которые являются простыми числами и отметить этот факт в специальном массиве.
4 балла
Разработайте линейный по времени и памяти алгоритм поиска всех простых чисел из заданного отрезка. Предоставьте описание алгоритма любым удобным для вас способом: псевдо-код, программный код, блок-схема и тд.
Подсказка: Обратите внимание на то что у каждого числа есть наименьший простой делитель
6 баллов
Проанализируйте время выполнения алгоритма, составив выражение точной функции сложности T(𝘕). Докажите что T(𝘕)=𝒪(𝘕) в соответствии с определением верхней ассимптотической границы сложности.
2 балла(?) - не включено в SET
Во время работы алгоритма сжато сохраняется вспомогательная информация. Покажите какая, и для вычисления чего ее можно использовать. Приведите подтверждение ее эффективности(например оценку сложности, доказывать точно не обязательно)
Решение
Приведем решение(код на 𝙲++):
void eratosphen_sieve(int N, std::vector<int>& primes) {
int least_prime[N + 1];
for (int i = 2; i <= N; ++i) {
if (least_prime[i] == 0) {
least_prime[i] = i;
primes.push_back(i);
}
for (int j = 0; j < primes.size(); ++j) {
if (primes[j] > least_prime[i] || i * primes[j] > N) {
break;
}
least_prime[i * primes[j]] = primes[j];
}
}
}
Критерием простоты в данном алгоритме выступает то что least_prime[i] == . Алгоритм корректен, так как вычисляет это значение для каждого числа на отрезке [1;𝘕] что и требуется в задаче, а по критерию можно определить простое число или нет.
Покажем теперь что алгоритм корректно вычисляет least_prime а заодно и докажем его время работы.
Если на текущей итерации i мы все еще не нашли никакого простого числа которое является делителем i, то и не сможем найти, так мы последовательно перебираем числа от меньших к большим, а значит все следующие числа больше i и не могут делить его.
Иначе у каждое составное число M можно представить единственным способом:
M=(p_M)⋅M/(p_M), где (p_M) - наименьшее простое число которое делит M, a M/(p_M)∈ℤ
И если на некоторой итерации i мы знаем (p_i) , то мы можем точно утверждать что для любого простого числа q меньшего (p_i) в произведении q⋅i;(p_q⋅i)=q(если поместится в наш отрезок), те таким образом мы находим для числа q⋅i его наименьший простой делитель, который единственнен. Посредством такого перебора мы не сможем еще раз рассмотреть тоже самое число, поскольку раз q наименьший, то i было наибольшим возможным делителем, которому не хватало 1 сомножителя до полного произведения, а все остальные комбинации будут меньше либо равны. В то время как i на следующих итерациях строго увеличится.
Теперь оценим функцию T(𝘕). Положим что операции индексирования, арифметика, и сравения можно оценить сверху одной константой c . Тогда:
c+2*c⋅𝘕 занимают операции в загаловке 1 цикла
≈3*c𝘕/ln(𝘕)+2*c операций занимает проверка if
Поскольку мы выяснили что для каждого составного числа least_prime вычисляется единожды, то вложенный цикл можно рассматривать "независимо" от внешнего.
Это значит что для каждого составного числа будет потрачено следующее количество элементарных операций, во вложенном цикле: 9*c+5*c=14*c (на условия и присваивание, соответственно). Тогда всего будет затрачено:
≈14*c*(𝘕-𝘕/ln(𝘕))+c*𝘕
T(𝘕)=c+3*c*𝘕+(3*c*𝘕)/ln(𝘕)+14*c*𝘕-(14*c*𝘕)/ln(𝘕)=
=18*c*𝘕-(11*c*𝘕)/ln(𝘕)≤18*c*𝘕 начиная с некоторого (𝘕_0)⇒T(𝘕)=𝒪(𝘕) ∎
Массив least_prime можно использовать для того что бы вычислять числа M из отрезка [1;𝘕], последовательно "отщипывая 1 простой множитель". Это может быть полезно при вычислении мультипликативных функциий, скажем функции Эйлера.
Длина факторизации не может привысить (log_2)(M), так как самый маленький простой делитель - 2 уменьшает значение числа M в 2 раза, то последовательное применение массива ограничивает длину этой функцией. Таким образом мы можем получить разложение всех чисел за время 𝒪(𝘕+log(M)) для любого числа M∈[1;𝘕] , в то время как например полная факторизация каждого числа требовала бы время 𝒪(𝘕√(,𝘕)) :
(∑_k=1^𝘕)(√(,k))≧(∫_1^𝘕)(√(,x)*d(x)) =(∣_1^N)(2/3*x3/2)=2/3*(𝘕√(,𝘕)-1)