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

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
Нет описания правки
 
(не показано 8 промежуточных версий этого же участника)
Строка 1: Строка 1:
===Проверка числа на простоту, O(sqrt(N))===
bool isPrime(int n) {
    if (n < 2)
        return 0;
   
    for (long long d = 2; d * d <= n; d++)
        if (n % d == 0)
            return 0;
   
    return 1;
}
===Получение списка делителей числа, O(sqrt(N))===
{| width="100%"
| width=50% |
vector<int> getDivisors(int n) {
    vector<int> divisors;
   
    for (long long d = 1; d * d <= n; d++) {
        if (n % d == 0) {
            divisors.push_back(d);
            if (d * d != n)
                divisors.push_back(n / d);
        }
    }
   
    sort(divisors.begin(), divisors.end());
    return divisors;
}
| width="10px" | &nbsp;
| width=50% |
vector<int> getPrimeDivisors(int n) {
    vector<int> primeDivisors;
   
    for (long long d = 2; d * d <= n; d++) {
        if (n % d == 0) {
            primeDivisors.push_back(d);
            while (n % d == 0)
                n /= d;
        }
    }
    if (n != 1)
        primeDivisors.push_back(n);
    return primeDivisors;
}
|}


O(NloglogN)
===Факторизация числа (получение списка простых делителей), O(sqrt(N))===
  const int N = 1000010;
{| width="100%"
  static bool p[N];
| width=50% |
  vector<int> factorize(int n) {
    vector<int> factorization;
   
    for (long long d = 2; d * d <= n; d++) {
        while (n % d == 0) {
            factorization.push_back(d);
            n /= d;
        }
    }
    if (n != 1)
        factorization.push_back(n);
   
    return factorization;
}
| width="10px" | &nbsp;
| width=50% |
  map<int, int> factorize(int n) {
    map<int, int> factorization;
    for (long long d = 2; d * d <= n; d++) {
        while (n % d == 0) {
            factorization[d]++;
            n /= d;
        }
    }
    if (n != 1)
        factorization[n]++;
   
   
for (int i = 2; i < N; i++)
    return factorization;
    if (!p[i] && 1LL * i * i < N)
}
        for (int j = i * i; j < N; j += i)
|}
            p[j] = 1;


O(N)
===Решето Эратосфена, O(NloglogN)===
  const int N = 1000010;
 
vector<int> primes;
  vector<int> getPrimes(int n) {
static int minDivisor[N];
    vector<int> isPrime(n + 1, 1), primes;
   
   
for (int i = 2; i < N; i++) {
    for (int i = 2; i < isPrime.size(); i++) {
    if (!minDivisor[i]) {
        if (isPrime[i]) {
        minDivisor[i] = i;
            primes.push_back(i);
        primes.push_back(i);
            for (long long j = 1LL * i * i; j < isPrime.size(); j += i)
                isPrime[j] = 0;
        }
     }
     }
     for (int j = 0; j < primes.size() && primes[j] <= minDivisor[i] && 1LL * i * primes[j] < N; j++)
        minDivisor[i * primes[j]] = primes[j];
     return primes;
  }
  }


== Ссылки на задачи ==
===Решето Эратосфена, O(N)===
* [http://acmp.ru/?main=task&id_task=200 ACMP #200 &mdash; Марсианские факториалы]
vector<int> getPrimes(int n) {
    vector<int> minDivisor(n + 1), primes;
    for (int i = 2; i < minDivisor.size(); 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] < minDivisor.size(); j++)
            minDivisor[i * primes[j]] = primes[j];
    }
    return primes;
}


== Ссылки ==
== Ссылки ==
* [http://e-maxx.ru/algo/eratosthenes_sieve E-Maxx — Решето Эратосфена]
Теория:
* [http://e-maxx.ru/algo/prime_sieve_linear E-Maxx — Решето Эратосфена с линейным временем работы]
:* [http://e-maxx.ru/algo/eratosthenes_sieve E-Maxx — Решето Эратосфена]
* [http://brestprog.by/topics/factorization Brestprog &mdash; Разложение числа на простые множители (факторизация). Делители числа]
:* [http://e-maxx.ru/algo/prime_sieve_linear E-Maxx — Решето Эратосфена с линейным временем работы]
* [http://brestprog.by/topics/primesieve Brestprog &mdash; Решето Эратосфена]
:* [http://brestprog.by/topics/factorization Brestprog &mdash; Разложение числа на простые множители (факторизация). Делители числа]
* [http://algorithmica.org/tg/number-theory algorithmica.org — Теория чисел]
:* [http://brestprog.by/topics/primesieve Brestprog &mdash; Решето Эратосфена]
* [http://algorithmica.org/ru/eratosthenes algorithmica.org — Решето Эратосфена]
:* [http://algorithmica.org/tg/number-theory algorithmica.org — Теория чисел]
* [http://informatics.mccme.ru/course/view.php?id=17 informatics.mccme.ru &mdash; Курс &laquo;Арифметика и числовые алгоритмы&raquo; &mdash; часть 1]
:* [http://algorithmica.org/ru/eratosthenes algorithmica.org — Решето Эратосфена]
* [http://github.com/indy256/codelibrary/blob/master/java/src/PrimesAndDivisors.java CodeLibrary &mdash; Prime numbers, sieve of Eratosthenes, Euler's totient function]
:* [https://usaco.guide/gold/divis?lang=cpp#prime-factorization USACO Guide — Prime Factorization]
Код:
:* [https://github.com/indy256/codelibrary/blob/master/cpp/numbertheory/primes_and_divisors.cpp indy256/codelibrary/cpp/numbertheory/primes_and_divisors.cpp]
:* [https://github.com/indy256/codelibrary/blob/master/cpp/numbertheory/factorization.cpp indy256/codelibrary/cpp/numbertheory/factorization.cpp]
Задачи:
:* [http://acmp.ru/?main=task&id_task=200 ACMP #200]
:* [[:Категория: Задачи: Простые числа|Задачи: Простые числа]]
:* [http://informatics.mccme.ru/course/view.php?id=17 informatics.mccme.ru &mdash; Курс &laquo;Арифметика и числовые алгоритмы&raquo; &mdash; часть 1]
 


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

Текущая версия от 17:04, 27 мая 2023

Проверка числа на простоту, O(sqrt(N))

bool isPrime(int n) {
    if (n < 2)
        return 0;
    
    for (long long d = 2; d * d <= n; d++)
        if (n % d == 0)
            return 0;
    
    return 1;
}

Получение списка делителей числа, O(sqrt(N))

vector<int> getDivisors(int n) {
    vector<int> divisors;
    
    for (long long d = 1; d * d <= n; d++) {
        if (n % d == 0) {
            divisors.push_back(d);
            if (d * d != n)
                divisors.push_back(n / d);
        }
    }
    
    sort(divisors.begin(), divisors.end());
    return divisors;
}

 
vector<int> getPrimeDivisors(int n) {
    vector<int> primeDivisors;
    
    for (long long d = 2; d * d <= n; d++) {
        if (n % d == 0) {
            primeDivisors.push_back(d);
            while (n % d == 0)
                n /= d;
        }
    }
    if (n != 1)
        primeDivisors.push_back(n);

    return primeDivisors;
}

Факторизация числа (получение списка простых делителей), O(sqrt(N))

vector<int> factorize(int n) {
    vector<int> factorization;
    
    for (long long d = 2; d * d <= n; d++) {
        while (n % d == 0) {
            factorization.push_back(d);
            n /= d;
        }
    }
    if (n != 1)
       factorization.push_back(n);
    
    return factorization;
}
 
map<int, int> factorize(int n) {
    map<int, int> factorization;

    for (long long d = 2; d * d <= n; d++) {
        while (n % d == 0) {
            factorization[d]++;
            n /= d;
        }
    }
    if (n != 1)
       factorization[n]++;

    return factorization;
}

Решето Эратосфена, O(NloglogN)

vector<int> getPrimes(int n) {
    vector<int> isPrime(n + 1, 1), primes;

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

    return primes;
}

Решето Эратосфена, O(N)

vector<int> getPrimes(int n) {
    vector<int> minDivisor(n + 1), primes;

    for (int i = 2; i < minDivisor.size(); 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] < minDivisor.size(); j++)
            minDivisor[i * primes[j]] = primes[j];
    }

    return primes;
}

Ссылки

Теория:

Код:

Задачи: