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ố.
Độ 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 $\sqrt{N}$. Khi đó $\frac{N}{D}$ phải lớn hơn $\sqrt{N}$. $N$ cũng chia hết cho $\frac{N}{D}$. Vì thế, nếu $N$ có ước nhỏ hơn $\sqrt{N}$ thì $N$ cũng có ước lớn hơn $\sqrt{N}$. Do đó, ta chỉ cần duyệt đến $\sqrt{N}$.
bool isPrime[int n] { for [int i = 2; i*i 1; }Độ phức tạp của thuật toán: Độ phức tạp của thuật toán là $O[\sqrt{N}]$ do ta phải duyệt từ 1 đến $\sqrt{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.
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 $\sqrt{N}$
- Đánh dấu các bội lớn hơn nó là số nguyên tố.