Eratosthenes

Sàng nguyên tố
Tìm ước nguyên tố nhỏ nhất của một số
Tìm ước nguyên tố lớn nhất của một số
Phân tích một số ra thừa số nguyên tố
Tính số lượng ước của một số
Tính tổng ước số của một số
Tính tích ước số của một số
Sàng nguyên tố trên đoạn [L..R]
Mở rộng - Linear Sieve

Sàng nguyên tố

Sàng Eratosthenes: https://vi.wikipedia.org/wiki/Sàng_Eratosthenes

Sàng Eratosthenes là thuật toán cơ bản và làm cơ sở cho các thuật toán ở dưới.

Độ phức tạp: \(O(Nlog(N))\)

const int N = 1e7+7;
bool isPrime[N];

void sieve() {
    memset(isPrime, true, sizeof isPrime);
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i*i < N; ++i) 
        if (isPrime[i])
            for (int j = i*i; j < N; j+=i)  
                isPrime[j] = false;
}

Tìm ước nguyên tố nhỏ nhất của một số

Độ phức tạp: \(O(Nlog(N))\)

const int N = 1e7+7;
int lp[N];

void sieve() {
    for (int i = 1; i < N; ++i) lp[i] = i;
    for (int i = 2; i*i < N; ++i) 
        if (lp[i] == i)
            for (int j = i*i; j < N; j+=i)  
                if (lp[j] == j) lp[j] = i;
}

Tìm ước nguyên tố lớn nhất của một số

Độ phức tạp: \(O(Nlog(N))\)

const int N = 1e7+7;
int mp[N];

void sieve() {
    for (int i = 1; i < N; ++i) mp[i] = i;
    for (int i = 2; i*i < N; ++i) 
        if (mp[i] == i)
            for (int j = i*i; j < N; j+=i)
                if (i < mp[j]) mp[j] = mp[j/i];
                else mp[j] = i;
}

Phân tích một số ra thừa số nguyên tố

const int N = 1e7+7;
int lp[N];

void sieve() {
    for (int i = 2; i < N; ++i) lp[i] = i;
    for (int i = 2; i*i < N; ++i) 
        if (lp[i] == i)
            for (int j = i*i; j < N; j+=i)
                if (lp[j] == j) lp[j] = i;
}

vector<pair<int,int>> factorize(int n) {
    vector<pair<int,int>> fac;
    while (n > 1) {
        int p = lp[n];
        fac.push_back(make_pair(p,0));
        while (n % p == 0) {
            fac.back().second++;
            n /= p;
        }
    }
    return fac;
}

Độ phức tạp:
- Tiền xử lí: \(O(Nlog(N))\)
- Phân tích thừa số nguyên tố: \(O(log(N))\)
Để phân tích một số \(n\) rất lớn ra thừa số nguyên tố, ta phải dùng thuật toán khác, thuật toán này sẽ được giải thích ở đây

Tính số lượng ước của một số

Độ phức tạp: \(O(Nlog(N))\)

const int N = 1e6+7;
int numDiv[N];

void sieve() {
    for (int i = 1; i < N; ++i)
    for (int j = i; j < N; j+=i)
        numDiv[j]++;
}

Cải tiến thuật toán:

Để tính số lượng ước của một số \(n\), ta làm như sau:

Phân tích \(n\) ra thừa số nguyên tố: \(n = {x_1}^{y_1} \times {x_2}^{y_2} \times \ldots \times {x_k}^{y_k}\), trong đó \(x_i\) là thừa số nguyên tố của \(n\), \(y_i\) là số mũ của \(x_i\) \((1 \le i \le k)\)
Sử dụng công thức tính số lượng ước dựa vào số mũ của các thừa số nguyên tố:

\[numDiv(n) = \prod_{i=1}^{k} (y_i+1)\]

const int N = 1e7+7;
int lp[N];

void sieve() {
    for (int i = 2; i < N; ++i) lp[i] = i;
    for (int i = 2; i*i < N; ++i)
        if (lp[i] == i)
            for (int j = i*i; j < N; j+=i)
                if (lp[j] == j) lp[j] = i;
}

int numDiv(int n) {
    int num = 1;
    while (n > 1) {
        int p = lp[n], cnt = 0;
        while (n % p == 0) {
            cnt++; n /= p;
        }
        num *= cnt+1;
    }
    return num;
}

Độ phức tạp:
- Tiền xử lí: \(O(Nlog(N))\)
- Tính số lượng ước: \(O(log(N))\)

Tính tổng ước số của một số

Độ phức tạp: \(O(Nlog(N))\)

const int N = 1e6+7;
int sumDiv[N];

void sieve() {
    for (int i = 1; i < N; ++i)
    for (int j = i; j < N; j+=i) {
        sumDiv[j] += i;
    }
}

Cải tiến thuật toán:

Để tính tổng ước số của \(n\), ta làm như sau:

Phân tích \(n\) ra thừa số nguyên tố, đặt \(n = {x_1}^{y_1} \times {x_2}^{y_2} \times {x_3}^{y_3} \times \ldots \times {x_k}^{y_k}\) với \(x_i\) là thừa số nguyên tố của \(n\), \(y_i\) là số mũ của \(x_i\) \((1 \le i \le k)\)
Sử dụng công thức tính tổng ước số của \(n\):

\[sumDiv(n) = \prod_{i=1}^{k} \sum_{j=0}^{y_i} {x_i}^j\]

Ta có thể tính công thức \(\sum_{i=0}^{n} x^i\) trong \(O(log(N))\), xem cách giải tại đây

const int N = 1e7+7;
int lp[N];

void sieve() {
    for (int i = 2; i < N; ++i) lp[i] = i;
    for (int i = 2; i*i < N; ++i)
        if (lp[i] == i)
            for (int j = i*i; j < N; j+=i)
                if (lp[j] == j) lp[j] = i;
}

long long Pow(long long a, int n) {
    long long res = 1;
    for (;n;n>>=1,a*=a)
        if (n&1) res*=a;
    return res;
}

int sumDiv(int n) {
    int sum = 1;
    while (n > 1) {
        int p = lp[n], cnt = 0;
        while (n % p == 0) {
            cnt++; n /= p;
        }
        sum *= (Pow(p, cnt+1)-1) / (p-1);
    }
    return sum;
}

Độ phức tạp:
- Tiền xử lý: \(O(Nlog(N))\)
- Tính tổng các ước: \(O(log(N)*log(log(N)))\), vì \(N \approx 10^7\) nên có thể có thể coi độ phức tạp là \(O(log(N))\)

Tính tích ước số của một số có modulo

Độ phức tạp: \(O(Nlog(N))\)

const int MOD = 1e9+7;
const int N = 1e6+7;
int prod[N];

void sieve() {
    for (int i = 0; i < N; ++i) prod[i] = 1;
    for (int i = 1; i < N; ++i)
    for (int j = i; j < N; j+=i) {
        prod[j] = 1LL * prod[j] * i % MOD;
    }
}

Cải tiến thuật toán:

Ngoài thuật toán trên, ta có thể dùng cách phân tích thành thừa số nguyên tố để đếm số lượng ước của một số từ đó tính được tích ước số của số đó:

Gọi \(x\) là số lượng ước của \(n\)
Tích ước số của \(n\) là: \(n^{x/2}\)

\[prodDiv(n) = \begin{cases} n^{x/2} \bmod MOD &, n \ne a^2 \\ n^{\lfloor x/2 \rfloor} \times \sqrt{n} \bmod MOD &, n = a^2 \end{cases} \ \ \ (a \in \mathbb{N})\]

Giải thích chi tiết tại đây

const int MOD = 1e9+7;
const int N = 1e7+7;
int lp[N];

void sieve() {
    for (int i = 2; i < N; ++i) lp[i] = i;
    for (int i = 2; i*i < N; ++i)
        if (lp[i] == i)
            for (int j = i*i; j < N; j+=i)
                if (lp[j] == j) lp[j] = i;
}

int numDiv(int n) {
    int num = 1;
    while (n > 1) {
        int p = lp[n], cnt = 0;
        while (n % p == 0) {
            cnt++; n /= p;
        }
        num *= cnt+1;
    }
    return num;
}

int Pow(int a, int n) {
    int res = 1;
    for (;n;n>>=1,a=1LL*a*a%MOD)
        if (n&1) res = 1LL*res*a%MOD;
    return res;
}

int mySqrt(int n) {
    int i = sqrt(n);
    while (i*i < n) i++;
    while (i*i > n) i--;
    return i;
}

int prodDiv(int n) {
    int x = numDiv(n);
    return x&1 ? 1LL*Pow(n,x/2)*mySqrt(n)%MOD : Pow(n,x/2);
}

Độ phức tạp:
- Tiền xử lý: \(O(Nlog(N))\)
- Tính tích ước số: \(O(logN))\)

Sàng nguyên tố trên đoạn [L..R]

Độ phức tạp: \(O(\sqrt{R}*log(R-L+1))\)

#include <bits/stdc++.h>

using namespace std;

const int N = 1e7+7;
bool isPrime[N];

void sieve(long long l, long long r) {
    memset(isPrime, true, sizeof isPrime);
    if (l == 0) isPrime[0] = isPrime[1] = false;
    else if (l == 1) isPrime[0] = false;
    for (long long i = 2; i*i <= r; ++i) 
    for (long long j = max(i*2,l+(i-l%i)%i); j <= r; j+=i)
        isPrime[j-l] = false;
}

int main() {
    long long l, r;
    cin >> l >> r;
    sieve(l, r);
    for (int i = l; i <= r; ++i) {
        cout << i << ' ' << isPrime[i-l] << '\n';
    }
    return 0;
}

Mở rộng - Linear Sieve

Ngoài cách sàng \(O(Nlog(N))\) còn có cách sàng \(O(N)\), có thể đọc tại đây