Простые числа. Решето Эратосфена: различия между версиями
Перейти к навигации
Перейти к поиску
Ctrlalt (обсуждение | вклад) (→Ссылки) |
Ctrlalt (обсуждение | вклад) (→Ссылки) |
||
| Строка 32: | Строка 32: | ||
* [http://brestprog.by/topics/primesieve Brestprog — Решето Эратосфена] | * [http://brestprog.by/topics/primesieve Brestprog — Решето Эратосфена] | ||
* [http://algorithmica.org/tg/number-theory algorithmica.org — Теория чисел] | * [http://algorithmica.org/tg/number-theory algorithmica.org — Теория чисел] | ||
* [http://algorithmica.org/ru/eratosthenes 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:Арифметические алгоритмы]] | ||
Версия от 12:04, 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];
}
Ссылки на задачи
Ссылки
- E-Maxx — Решето Эратосфена
- E-Maxx — Решето Эратосфена с линейным временем работы
- Brestprog — Разложение числа на простые множители (факторизация). Делители числа
- Brestprog — Решето Эратосфена
- algorithmica.org — Теория чисел
- algorithmica.org — Решето Эратосфена
- informatics.mccme.ru — Курс «Арифметика и числовые алгоритмы» — часть 1
- CodeLibrary — Prime numbers, sieve of Eratosthenes, Euler's totient function