Простые числа. Решето Эратосфена: различия между версиями

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
Нет описания правки
Строка 31: Строка 31:
* [http://brestprog.by/topics/factorization Brestprog — Разложение числа на простые множители (факторизация). Делители числа]
* [http://brestprog.by/topics/factorization Brestprog — Разложение числа на простые множители (факторизация). Делители числа]
* [http://brestprog.by/topics/primesieve Brestprog — Решето Эратосфена]
* [http://brestprog.by/topics/primesieve Brestprog — Решето Эратосфена]
* [http://algorithmica.org/tg/number-theory algorithmica.org — Теория чисел]
* [http://informatics.mccme.ru/course/view.php?id=17 informatics.mccme.ru — Курс «Арифметика и числовые алгоритмы» — часть 1]
* [http://informatics.mccme.ru/course/view.php?id=17 informatics.mccme.ru — Курс «Арифметика и числовые алгоритмы» — часть 1]
* [http://github.com/indy256/codelibrary/blob/master/java/src/PrimesAndDivisors.java CodeLibrary — Prime numbers, sieve of Eratosthenes, Euler's totient function]
* [http://github.com/indy256/codelibrary/blob/master/java/src/PrimesAndDivisors.java CodeLibrary — Prime numbers, sieve of Eratosthenes, Euler's totient function]


[[Category:Арифметические алгоритмы]]
[[Category:Арифметические алгоритмы]]

Версия от 11:59, 30 августа 2019

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

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

Ссылки