Thuật toán kiếm tra số nguyên tố – Freetuts

Trong bài này mình sẽ trình bày thuật toán để kiểm tra một số có phải là số nguyên tố hay không, sau khi giới thiệu xong thuật toán mình sẽ sử dụng ngôn ngữ C++ để giải mẫu cho các bạn. Trước tiên chúng ta tìm hiểu định nghĩa số nguyên tố là gì đã nhé.

Bài viết này được đăng tại

freetuts.net

, không được copy dưới mọi hình thức.

1. Số nguyên tố là gì?

Theo định nghĩa của Wikipedia thì số nguyên tố là số tự nhiên lớn hơn 1, chỉ có 2 ước là 1 và chính nó. Theo định nghĩa này thì những số 2, 3, 5, 7, 11, … là những số nguyên tố, trong đó số 2 là số nguyên tố chẵn duy nhất. Cũng như đặc thù của số nguyên dương, tất cả chúng ta chỉ tìm thấy số nguyên tố nhỏ nhất chứ không hề tìm thấy số nguyên tố lớn nhất .

Ví dụ: 7 là số nguyên tố vì trong khoảng từ 2 – 6 không tồn tại số nào mà 7 chia hết cả.

2. Thuật toán kiểm tra số nguyên tố

Dựa vào định nghĩa của số nguyên tố tất cả chúng ta sẽ có một số ít cách giải như sau ( những ví dụ được viết bằng ngôn từ C + + ) :Bài viết này được đăng tại [ không tính tiền tuts. net ]

Cách 1: Lặp từng phần tử với bước nhảy 1

Giả sử cần kiểm tra số n có phải là số nguyên tố hay không thì các bước thực hiện như sau:

• Bước 1: Nhập vào n
• Bước 2: Kiểm tra nếu n thì kết luận n không phải là số nguyên tố
• Bước 3: Lặp từ 2 tới (n-1), nếu trong khoảng này tồn tại số mà n chia hết thì kết luận n không phải là số nguyên tố, ngược lại n là số nguyên tố.

bool laSoNguyenTo1(int n)
{
	// Neu n

Hàm main:

void main()
{
	int n;
	cout > n;
		
	if (laSoNguyenTo1(n)){
		cout

Cách 2: Lặp từng phần tử với bước nhảy 2

Theo định nghĩa thì số 2 là số nguyên tố chẵn duy nhất, thế cho nên ta sẽ loại 2 ra khỏi vòng lặp và trong thân vòng lặp chỉ kiểm tra những số lẻ mà thôi, cách này sẽ tối ưu hơn cách 1 rất nhiều .

bool laSoNguyenTo2(int n)
{
	// Neu n

Hàm main:

void main()
{
	int n;
	cout > n;
		
	if (laSoNguyenTo2(n)){
		cout

3. Lời kết

Vẫn còn rất nhiều cách khác nhưng chung quy lại vẫn phải bám vào định nghĩa số nguyên tố là gì. Ví dụ trong vòng lặp điểm dừng sẽ là ( n / 2 ) thay vì ( n-1 ) vì theo kim chỉ nan thì 1 số ít không khi nào chia hết cho số một nửa của nó. Ví dụ số 9 thì số một nửa của nó là số ( 9 : 2 = 4 ), như vậy ta chỉ cần kiểm tra những số từ 2,3,4 mà thôi, còn những số 5,6,7,8 chắc chẵn 9 sẽ không chia hết .

for (int i = 3; i 

Source: https://thcsbevandan.edu.vn
Category : Thông tin cần biết