Вы можете выполнить Сито Эратосфена, чтобы определить, какие числа просты в диапазоне [2, n] в O(n) времени следующим образом:
Для каждого числа x в интервал [2, n], мы вычисляем минимальный простой множитель x. В целях реализации это легко сделать, сохранив массив --- скажем, MPF[] ---, в котором MPF[x] представляет минимальный простой коэффициент x. Первоначально вы должны установить MPF[x] равным нулю для каждого целого числа x. По мере выполнения алгоритма эта таблица будет заполнена.
Теперь мы используем for-l oop и выполняем итерацию от i = 2 до i = n (включительно). Если мы сталкиваемся с числом, для которого MPF[i] равно 0, то мы немедленно заключаем, что i является простым, поскольку оно не имеет наименьшего простого множителя. На этом этапе мы помечаем i как простое, вставляя его в список, и устанавливаем MPF[i] равным i. И наоборот, если MPF[i] делает не равным 0, то мы знаем, что i является составным с минимальным простым множителем, равным MPF[i].
На каждой итерации после проверки MPF[i] мы делаем следующее: вычисляем число y_j = i * p_j для каждого простого числа p_j, меньшего или равного MPF[i], и устанавливаем MPF[y_j] равным p_j ,
Это может показаться нелогичным - почему время выполнения O(n), если у нас есть два вложенных цикла? Ключевая идея заключается в том, что каждое значение установлено точно на единицу, поэтому время выполнения равно O(n). Этот веб-сайт предоставляет реализацию C ++, которую я привел ниже:
const int N = 10000000;
int lp[N+1];
vector<int> pr;
for (int i=2; i<=N; ++i) {
if (lp[i] == 0) {
lp[i] = i;
pr.push_back (i);
}
for (int j=0; j<(int)pr.size() && pr[j]<=lp[i] && i*pr[j]<=N; ++j)
lp[i * pr[j]] = pr[j];
}
Массив lp[] в приведенной выше реализации аналогичен MPF[], который я описал в мое объяснение. Кроме того, pr хранит список простых чисел.