Eratosthenes

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;
}

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]++;
}

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

\[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;
}

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:

\[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;
}

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ố đó:

\[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);
}

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