Hội đồng bộ môn Tin học - tỉnh An Giang

Kiểm tra số nguyên tố trong Pascal

Đề: Nhập vào số tự nhiên N (với 1< N <= 10 mũ 9). Xuất ra màn hình N có phải số nguyên tố hay không.
Ý tưởng: Số nguyên tố là số chia cho 1 và chính nó. Giả sử số vừa nhập vào là N, ta cho i chạy từ 2 đến N-1, nếu N chia hết cho i trong bất cứ lần lặp nào thì có nghĩa là N không nguyên tố, nếu không chia hết cho bất cứ lần lặp nào là nguyên tố. Về nguyên tắc là như vậy, nhưng người ta đã chứng minh được rằng chỉ cần xét từ 2 đến phần nguyên căn bậc 2 của N. Như thế thuật toán sẽ tối ưu hơn.

Chứng minh: Chỉ cần xét từ 2 đến phần nguyên căn bậc 2 của N thay vì xét đến N: 
Lấy ví dụ số không nguyên tố:
9=3*3
12=3*4
18=2*9=3*6
20=4*5=2*10
trong các ví dụ trên, các số không nguyên tố được phân tích thành tích các cặp ước của chúng, trong mỗi cặp số nhỏ đứng trước, số lớn đứng sau. Trong mỗi cặp, ta có thể thấy rõ một điều: số đứng trước (nhỏ hơn) luôn luôn nhỏ hơn hoặc bằng căn bậc hai của số cần xét. Ví dụ ta thấy 20=4*5, rõ ràng 4 nhỏ hơn căn bậc hai của 20. Bạn tự xét các ví dụ khác nhé. Có thể chứng minh được điều này bằng toán học như sau:
Chứng minh: Gọi số cần xét là n, căn bậc hai của nó là x, hai ước tương ứng có tích bằng n của nó là a và b(a<>b), ta cần chứng minh a<x hoặc b<x. Vì a và b có vai trò tương đương, nên ta giả sử a<b.
Giả sử a>x và b>x, ta có a*b>x*x=n => trái với giải thiết. Vậy trong hai số a và b, phải có một số nhỏ hơn x. 
Dựa vào đặc điểm trên, ta sẽ giới hạn phạm vi của i là 2->n-1 thành 2->sqrt(n). Tuy nhiên, sqrt(n) với n không chính phương sẽ ra số vô tỉ, trong khi i là số nguyên, vậy cần làm tròn sqrt(n). Phạm vi mới sẽ là 2->trunc(sqrt(n)).

Chương trình

Program kiem_tra_nguyen_to;

Uses crt;

Var N,i:int64; ok:boolean;

Begin

 Clrscr;

 ok:=true;

 write('nhap vao so can kiem tra tinh nguyen to: '); readln(n);

 if n<=1 then ok:=false;

 i:=2;

 while i<= trunc(sqrt(n)) do

   Begin

        if n mod i=0 then

           begin

                ok:=false;

                break;

           end

        else

           i:=i+1;

   end;

 if ok then write(N,'

 la nguyen to.')

 else write(N,' khong la nguyen to.');

 readln;

end.

Mở rộng bài toán:

    - Tìm số nguyên tố trong dãy số đã cho

    - Tìm số nguyên tố trong đoạn từ a đến b với a<b được nhập từ bàn phím.

    - Tìm số siêu nguyên tố

    - Nguyên tố sinh đôi

    - ............