Простые числа. Решето Эратосфена

Материал из Олимпиадное программирование в УлГТУ
Перейти к: навигация, поиск

O(NloglogN)

const int N = 1000010;
static bool p[N];

for (int i = 2; i < N; i++)
    if (!p[i] && 1LL * i * i < N)
        for (int j = i * i; j < N; j += i)
            p[j] = 1;

O(N)

const int N = 1000010;
vector<int> primes;
static int minDivisor[N];

for (int i = 2; i < N; i++) {
    if (!minDivisor[i]) {
        minDivisor[i] = i;
        primes.push_back(i);
    }
    for (int j = 0; j < primes.size() && primes[j] <= minDivisor[i] && 1LL * i * primes[j] < N; j++)
        minDivisor[i * primes[j]] = primes[j];
}

Ссылки на задачи

Ссылки