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:  

1.  Nhập số n;
2. 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;
3. 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

Categories: Phần mềm Toán học, Thuật toán

Các bài liên quan