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

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];
}

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

• ACMP #200 — Марсианские факториалы

Ссылки

• E-Maxx — Решето Эратосфена
• E-Maxx — Решето Эратосфена с линейным временем работы
• Brestprog — Разложение числа на простые множители (факторизация). Делители числа
• Brestprog — Решето Эратосфена
• algorithmica.org — Теория чисел
• algorithmica.org — Решето Эратосфена
• informatics.mccme.ru — Курс «Арифметика и числовые алгоритмы» — часть 1
• CodeLibrary — Prime numbers, sieve of Eratosthenes, Euler's totient function