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

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску

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

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

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

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

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

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

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

vector<int> getPrimes() {
    const int N = 1e6;
    vector<int> isPrime(N, 1), primes;
    
    for (int i = 2; i < N; i++) {
        if (isPrime[i]) {
            primes.push_back(i);
            for (long long j = 1LL * i * i; j < N; j += i)
                isPrime[j] = 0;
        }
    }
    
    return primes;
}

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

vector<int> getPrimes() {
    const int N = 1e6;
    vector<int> minDivisor(N), primes;
    
    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];
    }
    
    return primes;
}

Ссылки

Теория:

Код:

Задачи: