Cách kiểm tra nhanh N có phải là số nguyên tố

[huynguyen]

Bài toán này đã trở nên rất đỗi quen thuộc với chúng ta, trong bài này chúng ta sẽ bàn đến cách kiểm tra 1 số nguyên N cho trước có nguyên tố hay không trong phạm vi kiến thức số học sơ cấp.

Có rất nhiều cách, các cách thông thường là:
+ Xét các số từ 1 đến N xem có bao nhiêu số là ước của N rồi so sánh với 2. Cách này chạy rất chậm!
+ Xét các số từ 2 đến sqrt(N) rồi nếu là ước của N thì dừng lại, nhanh hơn 1 chút!

Ta sẽ bàn 1 cách nhanh hơn nữa:
Rõ ràng cái ta cần là làm sao giảm bớt số lượng số phải đem ra thử có phải là ước của N hay không. Trong danh sách này, có thể thừa (như 2 cách trên thừa rất nhiều) nhưng tuyệt đối không được thiếu các số nguyên tố bé hơn hoặc bằng sqrt(N). Vậy thì ta sẽ duyệt các số này theo 1 quy luật nào đó. Quy luật đó là gì?

Nhận xét: 1 số nguyên tố chia cho 6 dư 1 hoặc 5 (dễ dàng chứng minh) suy ra tập các số nguyên chia 6 dư 1 hoặc 5 sẽ bao trùm tập các số nguyên tố.

Từ đây ta có thuật toán: ta chỉ xét các số bé hơn hoặc bằng sqrt(N) mà chia 6 dư 1 hoặc 5 mà thôi, nếu N chia hết cho bất cứ 1 số nào trong đó thì N là hợp số, trái lại N là nguyên tố.

không phải ngẩu nhiên mà tôi chọn hằng số k= 6 này. Bài toán trở thành tìm số k mà từ 1 tới k-1 có ít số nguyên tố cùng nhau với nó nhất. Khi đó tỉ lệ phải xét chính là tỉ số các số nguyên tố cùng nhau này với k

thực nghiệm thì thấy số k tổng quát là tích của vài số nguyên tố đầu tiên, tất nhiên càng nhiều thì tỉ lệ phải xét càng nhỏ nhưng cài đặt có phần phức tạp hơn

các bạn mới làm toán thì bỏ qua tìm số k này, giỏi lên một tí các bạn cho k=2 để loại các số chẳn
rồi k=6 để loại các số chia hai huặc ba
nếu k=2*3*5=30( tỉ lệ phải xét, 4/15) thì tốc độ đc cải thiện đáng để, bạn thử cài đặt nhé, chú ý cái đặt thế nào cho thông minh

khi nghịch mã nguồn của Maple thì thấy nó lấy k là tích các số nguyên tố <1000 cơ

[hailoc12]

không phải ngẩu nhiên mà tôi chọn hằng số k= 6 này. Bài toán trở thành tìm số k mà từ 1 tới k-1 có ít số nguyên tố cùng nhau với nó nhất. Khi đó tỉ lệ phải xét chính là tỉ số các số nguyên tố cùng nhau này với k

Em chưa hiểu lắm chỗ này, tại sao phải tìm số k để có ít số nguyên tố cùng nhau với nó nhất.

[kidkid]

Hay lắm HuyNguyen . Những điều này học thì ko suy nghĩ ra , đọc một thấy thú vị .

Em chưa hiểu lắm chỗ này, tại sao phải tìm số k để có ít số nguyên tố cùng nhau với nó nhất.

VD như tớ xét số 19^2 có phải là số nguyên tó hay không thì thông thường phải duyệt đến số 19 . Trong quá trình đó ta có sự lặp lại giữa /2 rồi /4 đồng thời là /3 và /6 .
Nhìn đây nè :

rồi k=6 để loại các số chia hai huặc ba

Chắc đến đây là hiểu rồi .

[hailoc12]

* To kidkid: Dùng k=6 để loại các số chia hết cho 2, 3, 4, 6 thì em hiểu rồi nhưng tại sao phải chọn k là tích các số nguyên tố.

[toanmom]

Số là số chia hết cho chính nó và 1 vì thế nên ta có thể ko xét 1 mà chỉ xét từ sqrt của nó đến nó.Làm cách này tuy nó hơi khó hiểu chút nhưng rất nhanh đấy,cách này Thầy mình đã chấp nhận

[blackpawn]

Số là số chia hết cho chính nó và 1 vì thế nên ta có thể ko xét 1 mà chỉ xét từ sqrt của nó đến nó.Làm cách này tuy nó hơi khó hiểu chút nhưng rất nhanh đấy,cách này Thầy mình đã chấp nhận

Ủa, sao không xét từ 2 đến sqrt(n), như vậy có lẽ nhanh hơn

các bạn mới làm toán thì bỏ qua tìm số k này, giỏi lên một tí các bạn cho k=2 để loại các số chẳn
rồi k=6 để loại các số chia hai huặc ba
nếu k=2*3*5=30( tỉ lệ phải xét, 4/15) thì tốc độ đc cải thiện đáng để, bạn thử cài đặt nhé, chú ý cái đặt thế nào cho thông minh

khi nghịch mã nguồn của Maple thì thấy nó lấy k là tích các số nguyên tố <1000 cơ

Theo em hiểu thì khi xét số chia dạng mk + r < sqrt(n), ta sẽ bỏ không xét các số có USCLN(r, k) > 1 phải không ạ? Nếu tính trước thì chắc là nhanh, nhưng nếu đến lúc chạy mới xét thì chắc tốc độ cũng giảm đáng kể.
Có phải Maple dùng cách lưu sẵn các số này không ạ?

[toanmom]

ko biết sao chứ mỗi khi làm toán mình hay bỏ cái gì liên quan tới số 1 đi vì có nó vào thấy thêm rối hơn

[lag_nao]

Nhận xét: 1 số nguyên tố chia cho 6 dư 1 hoặc 5 (dễ dàng chứng minh) suy ra tập các số nguyên chia 6 dư 1 hoặc 5 sẽ bao trùm tập các số nguyên tố.

thế 2 và 3 thì sao

Định lý nhỏ Fecma áp dụng vào mà máy tính tính toán được kết quả lớn thì rất hay

[duc_khanh_89]

hình như chưa đc đâu anh ạ vì số 25 chia 6 dư 1 mà có phải snt đâu

[nhocxinh]

Uh nhỉ.Vì số 49 chia 6 dư 1 cũng đâu phải số nguyên tố