Kiểm tra Số nguyên tố

Định nghĩa:

Số nguyên tố là số có đúng hai ước số là 1 và chính nó. Tức là ngoài số 1 và chính nó, nó sẽ không chia hết cho bất kì số nào nữa. Ví dụ số 5 hay số 43 là số nguyên tố, bởi vì:

• 5 chỉ chia hết cho 1 và 5.
• 43 chỉ chia hết cho 1 và 43.

Kiểm tra số nguyên tố theo định nghĩa:

Đây là cách đơn giản và dễ dàng cài đặt nhất. Giả sử bạn cần kiểm tra xem n có phải là số nguyên tố hay không? Bạn chỉ cần kiểm tra xem n có chia hết cho bất kì số nào trong khoảng từ 1 đến n ( khoảng là không lấy hai đầu mút ).

Ví dụ: $n = 7$, thì bạn cần xét lần lượt, $7/2$, $7/3$, $7/4$, $7/5$, $7/6$.

Bạn có thấy cách trên xét rất nhiều không? Có cách để xét ít hơn, và tôi đoán đa số mọi người sử dụng. Thay vì bạn xét từ $2 \rightarrow (n-1)$, thì bạn chị cần xét từ $2 \rightarrow \sqrt{n}$.

Chứng minh:

Giả sử n không là số nguyên tố thì ta luôn tách ra được

$n=k_1 . k_2$ và $0 < k_1 \leqslant k_2 < n$.

$$\begin{aligned} k_1.k_2 \leqslant n \\ \Rightarrow k_1^2 \leqslant n \\ \Leftrightarrow k_1 \leqslant \sqrt{n} \\ \end{aligned} $$

Vậy bạn có thể hiểu đơn giản là $k_1$ lớn nhất cũng chỉ là $\sqrt{n}$, mà nếu bạn có $k_1$​ thì chắc chắn là số đó không phải là số nguyên tố. Vậy bạn chỉ cần xét giá trị $2 \rightarrow \sqrt{n}$

Vậy để cải tiến, bạn cần có những nhận xét sau:

Số nguyên tố là số lẻ, vì nếu số chẵn thì $k_1​=2$ vậy chắc chắn không phải là số nguyên tố. Vậy bạn có thể sử dụng bước nhảy là $2$ để xét.

#include <iostream>
#include <cmath>

using namespace std;

/*Thuật toán:
+ Số 1 không phải là số nguyên tố.
+ Số 2 là số chẵn duy nhất là số nguyên tố.
+ Số nguyên tố đều là số lẻ => số chia cũng phải là số lẻ. Vì số lẻ không thể chia hết cho số chẵn được.
*/

//Hàm kiểm tra số Nguyên tố.
bool isPrime(int n){
  if(n == 2) return true;
  else if(n == 1 || n % 2 == 0) return false;
  else{
    for(int i = 3; i <= sqrt(n); i+=2){
      if(n % i == 0) return false;
    }
  }
  return true;
}

int main(){
  int n = 25;
  cout << isPrime(n);
  return 0;
}

Tham khảo:

Tài liệu chuyên Tin học Quyển 1 - Hồ Sĩ Đàm