Простые числа. Решето Эратосфена: различия между версиями
Перейти к навигации
Перейти к поиску
Ctrlalt (обсуждение | вклад) Нет описания правки |
Ctrlalt (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
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]; | |||
} | |||
== Ссылки на задачи == | == Ссылки на задачи == | ||
* [http://acmp.ru/?main=task&id_task=200 ACMP #200 — Марсианские факториалы] | * [http://acmp.ru/?main=task&id_task=200 ACMP #200 — Марсианские факториалы] | ||
== Ссылки == | == Ссылки == | ||
* [http://e-maxx.ru/algo/eratosthenes_sieve e-maxx.ru | * [http://e-maxx.ru/algo/eratosthenes_sieve E-Maxx — Решето Эратосфена] | ||
* [http://brestprog. | * [http://e-maxx.ru/algo/prime_sieve_linear E-Maxx — Решето Эратосфена с линейным временем работы] | ||
* [http://brestprog. | * [http://brestprog.by/topics/factorization Brestprog — Разложение числа на простые множители (факторизация). Делители числа] | ||
* [http://brestprog.by/topics/primesieve Brestprog — Решето Эратосфена] | |||
* [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:Арифметические алгоритмы]] | ||
Версия от 13:37, 26 апреля 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];
}
Ссылки на задачи
Ссылки
- E-Maxx — Решето Эратосфена
- E-Maxx — Решето Эратосфена с линейным временем работы
- Brestprog — Разложение числа на простые множители (факторизация). Делители числа
- Brestprog — Решето Эратосфена
- informatics.mccme.ru — Курс «Арифметика и числовые алгоритмы» — часть 1
- CodeLibrary — Prime numbers, sieve of Eratosthenes, Euler's totient function