Đị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ì:
Đâ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à mình đoán đa số mọi người sử dụng. Thay vì bạn xét từ 2 => n - 1 thì bạn chỉ cần xét từ 2 => sqrt(n)
Vì không thể chèn công thức toán học vô nên mình sẽ chụp hình lại cho dễ nhì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ì k1 = 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.
Tham khảo:
Tài liệu chuyên Tin học Quyển 1 – Hồ Sĩ Đàm
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.
Đâ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à mình đoán đa số mọi người sử dụng. Thay vì bạn xét từ 2 => n - 1 thì bạn chỉ cần xét từ 2 => sqrt(n)
Vì không thể chèn công thức toán học vô nên mình sẽ chụp hình lại cho dễ nhì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ì k1 = 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.
C++:
#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