Thuật toán kiểm tra tính nguyên tố

31/7/13

Thuật toán kiểm tra tính nguyên tố

Kiểm tra tính nguyên tố (tiếng Anh: primality test) là bài toán kiểm tra xem một số tự nhiên

$n$ có phải là số nguyên tố hay không.
Yêu cầu: Nhập vào một số tự nhiên n. Xác định xem số đó có phải số nguyên tố hay không.
Phương pháp đơn giản nhất để kiểm tra một số

$n$ có là số nguyên tố không là kiểm tra xem nó có chia hết cho các số

$m$ nằm trong khoảng 2 đến

$n-1$ hay không. Nếu

$n$ chia hết cho một số

$m$ nào đó thì

$n$ là hợp số (composite), ngược lại

$n$ là số nguyên tố.
Thực ra việc kiểm tra với

$m$ từ 2 đến

$n-1$ là không cần thiết, mà chỉ cần kiểm tra đến

$\sqrt(n)$ . Đó là vì nếu

$n$ là hợp số thì nó chắc chắn có ước số không vượt quá

$\sqrt(n)$ .

Thuật toán:

Nhập số n;
Cho i chạy từ 2 đến phần nguyên của $\sqrt(n)$ .; Kiểm tra xem n có chia hết cho i hay không;
Nếu n chia hết cho i trong lần lặp nào đó, dừng thuật toán, kết luận n là hợp số;
Nếu n không chia hết cho i trong tất cả các lần lặp, kết luận n là số nguyên tố.

Lập trình với Scilab:

disp("+---+---+---+---+---+---+---+---+---+---+---+")
disp("     KIỂM TRA SỐ NGUYÊN TỐ")
disp("                             ")
//
clear
n=input("Nhập số cần kiểm tra tính nguyên tố: ")

// Hàm kiểm tra tính chia hết của hai số
function ch=kiemtra(x, y)
    d=floor(x/y)*y-x
    if d==0 then ch=1       // ch=1 là x chia hết cho y
        else ch=0           // ch=0 là không chia hết
    end
endfunction

// Kiểm tra tính nguyên tố
function kt=prem(q)
    m=floor(sqrt(q))
    kt=1                            // kt=1 tức q là số nguyên tố
    for i=2:m
        if kiemtra(q,i)==1 then 
            kt=0                    // kt=0 tức q KHÔNG nguyên tố
            break
    end
    end
endfunction

// Hiển thị kết quả
if prem(n)==1 then disp(" Số vừa nhập là số nguyên tố.") 
    else disp(" Số vừa nhập KHÔNG là số nguyên tố.") 
end