Thuật Toán Kiểm Tra Số Nguyên Tố

Em xin lỗi vì format code hơi tệ ạ.

Giáo này không đỡ được đâu. Thôi cứ ghi tới n-1 đi.

Cách bạn làm cũng đúng nhưng nếu bạn vẫn đang dao động thì nó ntn: Nếu n là hợp số thì phải có số p > 1 để n chia hết cho p, nhưng mà như vậy thì n cũng chia hết cho n/p, mà một trong hai số không thể vượt quá sqrt(n) (*). Lập luận này là dạng contrapositive.

Ý (*) có thể được chứng minh trực tiếp hoặc gián tiếp, nhưng một lần gián tiếp là đã thấy phức tạp rồi (chia tới sqrt(n) là biết nguyên tố -> hợp số phải có ước nhỏ hơn sqrt(n))

Bạn sai ở chỗ viết một đoạn code mà không biết nó hoạt động như thế nào và tại sao nó chạy được.
Bạn áp dụng một algorithm với sqrt mà không biết tại sao phải dùng nó. Để khi cô bạn cần bạn phản biện lại không biết làm thế nào để bảo vệ quan điểm của mình.
Mình không biết cụ thể nên không đánh gía cô của bạn, có thể cô bạn đang nói về chương trình chính. còn bạn thì đang làm chương trình con. Có hiểu lầm không ?

Cón đúng như a @rogp10 chỉ thì trong trường hợp này thì dùng sqrt 100% là chính xác.

Vâng, e sẽ tìm hiểu ngay bây giờ ạ ^^ cám ơn các a đã tư vấn

Trường hợp 1 : Nếu xét đến dưới sqrt(X) mà gặp số chia hết thì ko phải là số nguyên tố ( đương nhiên).
Trường hợp 2: Nếu xét đến trên sqrt(X) mà chưa gặp số chia hết thì kết luận được là đó là số nguyên tố vì
nếu tồn tại 2 số nguyên sao cho ab=X thì a,b >= sqrt(X) mà ab > X^2 vì a,b thuộc đoạn (sqrt(X),X) phản lại điều giả sử => chỉ cần xét đến sqrt(X)

Ở lớp thì nên dùng X div 2 được rồi vì dễ phản biện hơn
Có vẻ code trên ko xét trường hợp X = 2 thì true rồi

e mới đi tìm hiểu thì biết hợp số sẽ có ít nhất một ước từ khoảng 2 đến căn bậc 2 của nó :V nên có lẽ e phản biện được rồi
nguồn: wiki

À mà bỏ +1 nhé vướng số 2 đấy.

vâng e biết rồi ạ. ^^

Để chặt chẽ hơn ta quay lại định nghĩa của số nguyên tố và hợp số.

Tính nguyên tố (primality) luôn bao gồm tính bất khả phân (irreducible). Nghĩa là không thể viết được một số thành tích p*q mà p, q không phải là pt đơn vị. Xin nhắc lại 1 là phần tử đơn vị a*1 = 1*a = a Những số còn lại đều là hợp số.

Từ định nghĩa trên suy ra cả p lẫn q không thể quá sqrt(n), hay chia tới sqrt là được.

Tại sao lại chia thành ba loại: đơn vị, số nguyên tố và hợp số? Bởi vì không chỉ có 1 mới chia hết 1. Không cần xa xôi, số nguyên đã có +/-1 chia hết 1. Vậy -1 cũng phải là đơn vị.

0 thực ra là bị “hắt hủi” thì đúng hơn. Có một khái niệm là “zero divisor”, tức là không phải 0 mà nhân với nhau ra 0, nghĩa là ab == 0 =X=> a == 0 || b == 0. Tính bất khả phân không thể dùng thay nguyên tố.

có thể bạn không biết… để tìm nhanh hơn ta dùng chút lập luận để giản lược…
c1 : cứ chẵn là không phải nguyên tố rồi ( trừ thằng 2 ra ) vòng lặp đã giảm 1 nữa
c2: cứ là bội số của các số 1 2 3 4 5 thì không phải là số nguyên tối tức là 1n 2n 3n 4n 5n ,
c3 :rồi đến cái bá cháy nhất : số nguyên tố trừ số 2 3 5 thì đều có dạng 6n+1 hoặc 6n-1 ( đều có dạng đó chứ không phải hoàn toàn, check lại c1 và c2 là được) ví dụ với n=2 tức là 11 (62 -1) và 13 (62+1) 13 là nguyên tố với n=3 tức là 17 (63 -1) và 13 (63+1) 19 là nguyên tố với n=4 tức là 23 (64 -1) là nguyên tố và 13 (6*4+1) 25 không là nguyên tố vì nó là bội của 5 rồi ( check lại thằng c2)

Thực ra chạy sàng thì số phép mod còn giảm nữa 9 chữ số thì tối đa khoảng 9000 phép chia, nhưng RM chỉ cần 900 phép chia.