Nguồn: HackerEarth và 1 số bài viết trên Wikipedia

Người dịch: Bùi Việt Dũng

Bạn có thể đọc phần 1 về Modulo & GCD ở đây.

Số nguyên tố (Prime Numbers)

Số nguyên tố là số nguyên lớn hơn 1 và có đúng 2 ước là 1 và chính nó.

Hợp số (Composite numbers) là số nguyên lớn hơn 1 và có nhiều hơn 2 ước.

Ví dụ, 5 là số nguyên tố vì 5 chỉ chia hết cho 1 và 5. Tuy nhiên, 6 là hợp số vì 6 chia hết cho 1, 2, 3 và 6.

Có rất nhiều phương pháp để kiểm tra một số nguyên có phải là số nguyên tố hay không.

Thuật toán "ngây thơ"

Ta sẽ duyệt hết tất cả các số từ 1 đến N và đếm số ước của N. Nếu số ước của N là 2 thì N là số nguyên tố, nếu không thì N không là số nguyên tố.

bool isPrime(int n) {
    for (int i = 2; i < n; i++)
        if (n % i == 0) {
            // n chia hết cho số khác 1 và chính nó.
            return false;
        }
    return n > 1;
}

Độ phức tạp của thuật toán: Độ phức tạp của thuật toán là O(N) do ta phải duyệt hết các số từ 1 đến N.

Một thuật toán tốt hơn

Xét hai số nguyên dương N và D thỏa mãn N chia hết cho D và D nhỏ hơn N. Khi đó ND phải lớn hơn NN cũng chia hết cho ND. Vì thế, nếu N có ước nhỏ hơn N thì N cũng có ước lớn hơn N. Do đó, ta chỉ cần duyệt đến N.

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

Độ phức tạp của thuật toán: Độ phức tạp của thuật toán là O(N) do ta phải duyệt từ 1 đến N.

Sàng Eratosthenes (Sieve of Eratosthenes)

Sàng Eratosthenes dùng để tìm các số nguyên tố nhỏ hơn hoặc bằng số nguyên N nào đó. Nó còn có thể được sử dụng để kiểm tra một số nguyên nhỏ hơn hoặc bằng N hay không.

text

Nguyên lí hoạt động của sàng là vào mỗi lần duyệt, ta chọn một số nguyên tố và loại ra khỏi sàng tất cả các bội của số nguyên tố đó mà lớn hơn số đó. Sau khi duyệt xong, các số còn lại trong sàng đều là số nguyên tố.

Mã giả (Pseudo Code):

  • Đánh dấu tất cả các số đều là số nguyên tố.

  • Với mỗi số nguyên tố nhỏ hơn N

    • Đánh dấu các bội lớn hơn nó là số nguyên tố.
void sieve(int N) {
    bool isPrime[N+1];
    for(int i = 0; i <= N;++i) {
        isPrime[i] = true;
    }
    isPrime[0] = false;
    isPrime[1] = false;
    for(int i = 2; i * i <= N; ++i) {
         if(isPrime[i] == true) {
             // Mark all the multiples of i as composite numbers
             for(int j = i * i; j <= N; j += i)
                 isPrime[j] = false;
        }
    }
}

Code trên được dùng để tìm các số nguyên tố nhỏ hơn hoặc bằng N.

Độ phức tạp của thuật toán:

Số lần lặp của vòng lặp trong là:

  • Khi i=2, vòng lặp trong lặp N2 lần.
  • Khi i=3, vòng lặp trong lặp N3 lần.
  • Khi i=5, vòng lặp trong lặp N5 lần.

Độ phức tạp tổng: N.(12+13+15+)=O(NlogN).

Phân tích thừa số nguyên tố với sàng Eratosthenes

Cách cài đặt:

Đầu tiên hãy xem xét thuật toán phân tích ra thừa số nguyên tố trong O(N).

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

Tại mỗi bước ta phải tìm số nguyên tố nhỏ nhất mà N chia hết cho số đó. Do đó, ta phải biến đổi sàng Eratosthenes để tìm được số mình mong muốn trong O(1).

int minPrime[n + 1];
for (int i = 2; i * i <= n; ++i) {
    if (minPrime[i] == 0) { //if i is prime
        for (int j = i * i; j <= n; j += i) {
            if (minPrime[j] == 0) {
                minPrime[j] = i;
            }
        }
    }
}
for (int i = 2; i <= n; ++i) {
    if (minPrime[i] == 0) {
        minPrime[i] = i;
    }
}

Bây giờ ta có thể phân tích một số ra thừa số nguyên tố trong O(logN).

vector<int> factorize(int n) {
    vector<int> res;
    while (n != 1) {
        res.push_back(minPrime[n]);
        n /= minPrime[n];
    }
    return res;
}

Điều kiện sử dụng phương pháp này là ta phải tạo được mảng có độ dài N phần tử.

Phương pháp này rất hữu ích khi ta phải phân tich nhiều số nhỏ ra thừa số nguyên tố. Ta không cần thiết phải sử dụng phương pháp này trong mọi bài toán liên quan đến phân tích một số ra thừa số nguyên tố. Ngoài ra, ta không thể sử dụng phương pháp này nếu N bằng 109 hay 1012. Khi đó, ta chỉ có thể sử dụng thuật toán O(N).

Tính chất thú vị: Nếu N=p1q1.p2q2pkqk với p1,p2,,pk là các số nguyên tố thì N có (q1+1).(q2+1)(qk+1) ước phân biệt.

Sàng Eratosthenes trên đoạn

Đôi khi bạn phải tìm tất cả các số không phải trên đoạn [1;N] mà là trên đoạn [L;R] với R lớn.

Điều kiện sử dụng phương pháp này là bạn có thể tạo mảng độ dài RL+1 phần tử.

Cài đặt:

vector<bool> isPrime(R - L + 1, true);  // x là số nguyên tố khi và chỉ khi isPrime[x - l] == true

for (long long i = 2; i * i <= R; ++i) {
    for (long long j = max(i * i, (L + i - 1) / i * i); j <= R; j += i) {
        isPrime[j - L] = false;
    }
}

if (1 >= L) {  // Xét riêng trường hợp số 1
    isPrime[1 - L] = false;
}

for (long long x = L; x <= R; ++x) {
    if (isPrime[x - L]) {
        // i là số nguyên tố
    }
}

Độ phức tạp của thuật toán là O(Rk) với k là hằng số.

Lưu ý: Nếu bạn chỉ cần kiểm tra tính nguyên tố của một hay một vài số thì ta không nhất thiết phải xây dựng sàng. Ta có thể sử dụng hàm sau để kiểm tra tính nguyên tố của một số.

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

Bài tập áp dụng:

Post a Comment

Mới hơn Cũ hơn