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

Проверка числа на простоту, 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; }

bool isPrime(int n) { if (n < 2) return 0; static vector<int> primes = getPrimes(1e5); for (int i = 0; 1LL * primes[i] * primes[i] <= n; i++) if (n % primes[i] == 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;
}

Ссылки

Теория:

• E-Maxx — Решето Эратосфена
• E-Maxx — Решето Эратосфена с линейным временем работы
• Brestprog — Разложение числа на простые множители (факторизация). Делители числа
• Brestprog — Решето Эратосфена
• algorithmica.org — Теория чисел
• algorithmica.org — Решето Эратосфена
• USACO Guide — Prime Factorization

Код:

• indy256/codelibrary/cpp/numbertheory/primes_and_divisors.cpp
• indy256/codelibrary/cpp/numbertheory/factorization.cpp

Задачи:

• ACMP #200
• Задачи: Простые числа
• informatics.mccme.ru — Курс «Арифметика и числовые алгоритмы» — часть 1