Thuật toán tìm số nguyên tố trong pascal năm 2024

Bài toán kiểm tra một số có phải là số nguyên tố không là một bài toán hết sức cơ bản khi bạn học bất kì một ngôn ngữ lập trình nào, trong bài viết này mình chia sẻ với các bạn thuật toán kiểm tra số nguyên tố trong pascal đơn giản và dễ hiểu nhất, nó không phải là thuật toán tối ưu nhưng dễ hiểu và phù hợp với đối tượng học sinh THCS dưới đây hãy tham khảo với onthihsg để có cách tìm số nguyên tố.

Nội dung bài toán kiểm tra số nguyên tố trong pascal

Viết chương trình kiểm tra một số n (n <2 tỉ) có phải là số nguyên tố hay không.

Hướng dẫn Hàm kiểm tra số nguyên tố :

Dữ liệu vào file: nguyento.inp Dữ liệu ra file: nguyento.out Chứa số n Yes (No)

Ý tưởng của thuật toán: Kiểm tra đúng như định nghĩa số nguyên tố, ta chỉ cần xem số đó có lớn hơn 1 không và có bao nhiêu ước, nếu chỉ có hai ước thì là số nguyên tố còn ngược lại thì không phải.

Thuật toán tìm số nguyên tố

Chương trình viết hàm kiểm tra số nguyên tố viết bằng Free pascal

program kiem_tra_nguyen_to; var m:longint;f:text; {-- chuong trinh con kiem tra so nguyen to } function ngto(n:longint):boolean; var i:longint; begin if n<2 then ngto:=false else ngto:=true; for i:=2 to trunc(sqrt(n)) do if n mod i = 0 then

                 begin  
                    ngto:=false;  
                    break; {thoat vong lap}  
                 end;  

end; {- het CT con----} {Than chuong trinh chinh --} begin {Doc file } assign(f,'nguyento.inp'); reset(f); readln(f,m);close(f); {Mo file de ghi} assign(f,'nguyento.out'); rewrite(f); if ngto(m) then write(f,'yes') else write(f,'no'); close(f); end. Hầu hết những chương trình mà mình viết đều sử dụng chương trình con, theo mình nên tập cho học sinh thói quen như vậy ngay từ những bài tập đầu tiên.

Bạn cũng có thể tham khảo chương trình kiểm tra số nguyên tố trong Scratch

Sau khi học sinh nắm được thuật toán kiểm tra số nguyên tố ta có thể phát triển thêm một số bài toán liên quan như sau:

Một số bài toán về số nguyên tố

Bài 1.1. Viết chương trình nhập vào một số n, xuất ra những số nguyên tố nhỏ hơn hoặc bằng n và tổng của tất cả những số nguyên tố đó.

Dữ liệu vào file: Sum_nt.inp Dữ liệu ra file: Sum_nt.out Chứa số n – Dòng 1: chứa các số nguyên tố <=n cách nhau 1 khoảng trắng

– Dòng 2: Chứa tổng các số nguyên tố trên

Bài tập trên mình yêu cầu học sinh sử dụng chương trình co để giải quyết qua đó rèn luyện cho học sinh tư duy kế thừa

Ý tưởng của thuật toán:

• Có một chương trình con kiểm tra số nguyên tố
• Ta chỉ cần duyệt từ 1 đến n xem có số nào là số nguyên tố không để đếm và cộng dồn.

program Dem_nguyen_to; var m,k,s:longint;f:text; {-- chuong trinh con kiem tra so nguyen to } function ngto(n:longint):boolean; var i:longint; begin if n<2 then ngto:=false else ngto:=true; for i:=2 to trunc(sqrt(n)) do if n mod i = 0 then

                 begin  
                    ngto:=false;  
                    break; {thoat vong lap}  
                 end;  

end; {- het CT con----} {Than chuong trinh chinh --} begin {Doc file } assign(f,'sum_nt.inp'); reset(f); read(f,m);close(f); {Mo file de ghi} assign(f,'sum_nt.out'); rewrite(f); k:=1; S:=0; while k<=m do

begin  
  if ngto(k) then begin write(f,k,' ');  s:=s+k; end;  
  k:=k+1;  
end;

writeln(f); write(f,S); close(f); end. Bài 1.2. Viết chương trình phân tích một số tự nhiên n (n <2 tỉ) ra thừa số nguyên tố.

Dữ liệu vào file: pt_nt.inp Dữ liệu ra file: pt_nt.out Chứa số n

VD: 100

1 dòng: chứa kết quả

VD: 2.2.5.5

Đối với bài toán này ta chia số đó (nếu chia hết) cho số nguyên tố (duyệt từ số nguyên tố nhỏ đến lớn).

Kiểm tra xem một số n có phải là số nguyên tố hay không vốn là một bài toán đơn giản chúng ta đều tiếp xúc từ khi mới bập bẹ những bài toán lập trình đầu tiên. Tuy nhiên, để đáp ứng những nhu cầu lớn lao của các ngành khoa học máy tính hiện nay như cryptography - mật mã hóa, những thuật toán kiểm tra số nguyên tố cần phải vượt xa giới hạn 32 bit nhỏ nhoi mà bình thường chúng ta hay sử dụng.

Hôm nay chúng ta sẽ phân tích những thuật toán nền tảng để kiểm tra số nguyên tố - từ "thô sơ" đến "hiện đại"!

1. Thuật toán kiểm tra nguyên tố là gì?

Thuật toán kiểm tra nguyên tố là những thuật toán để kiểm tra xem một số n có phải là số nguyên tố hay không. Không giống như thuật toán phân tích thừa số nguyên tố, kiểm tra nguyên tố đơn giản hơn nhiều về mặt tính toán, bước thực hiện, và thời gian chạy.

Hầu hết những thuật toán kiểm tra nguyên tố sẽ chứng minh số n có phải là hợp số hay không, vì thế tên gọi chính xác của những thuật toán như vậy sẽ là kiểm tra hợp số. Tuy nhiên chúng đều hướng tới một mục tiêu là tìm kiếm những số nguyên tố.

2. Những kiểm tra đơn giản

Dựa vào định nghĩa của số nguyên tố (là số chỉ chia hết cho 1 và chính nó), ta sẽ có được thuật toán kiểm nguyên tố đơn giản nhất:

Kiểm tra các số từ 2 đến n - 1, nếu n chia hết cho một trong những số đó thì n không phải là số nguyên tố. Ngược lại thì n là số nguyên tố.

Độ phức tạp thời gian (ĐPT) của thuật toán trên là O(n)

Tuy nhiên, giống như thuật toán đếm số ước của n, ta hoàn toàn có thể cải tiến để giảm ĐPT:

Kiểm tra các số từ 2 đến √n, nếu n chia hết cho một trong những số đó thì n không phải là số nguyên tố. Ngược lại thì n là số nguyên tố.

ĐPT: `n`3

Tuy nhiên, chúng ta còn có thể phát triển tiếp thuật toán trên bằng cách chứng minh n không chia hết cho những số nguyên tố nhỏ hơn nó.

Để ý rằng tất cả những số nguyên tố lớn hơn 3 đều có dạng `n`5 (vì `n`6 là những số chẵn; `n`7 chia hết cho 3). Vậy phương pháp kiểm tra lúc này sẽ là:

Kiểm tra các số có dạng n`8 từ 2 đến √n`, nếu n chia hết cho một trong những số đó thì n không phải là số nguyên tố. Ngược lại thì n là số nguyên tố.

// pseudocode - mã giả cho phương pháp kiểm tra nguyên tố trên
function is_prime(n)
    if n ≤ 3 then
        return n > 1
    else if n mod 2 = 0 or n mod 3 = 0
        return false
    let i = 5
    while i × i ≤ n do
        if n % i = 0 or n % (i + 2) = 0
            return false
        i = i + 6
    return true

Để ý rằng chúng ta bắt đầu vòng lặp từ n`3 (có dạng `n`4), kiểm tra `n chia n`6 và `n chia n`8, và tăng `n`6 lên 6 sau mỗi bước. Như vậy ta có thể duyệt tất cả các số có dạng `n`5 không vượt quá √n`.

ĐPT: `n - 1`2 (cũng là `n`3, nhưng nhanh hơn vài mili giây)

Bây giờ, thay vì 6, chúng ta có thể sử dụng 30. Thay vì 30, chúng ta có thể sử dụng tích của n số nguyên tố đầu tiên.

Thế nhưng phương pháp này vẫn chưa đủ dù chỉ đối với những số nguyên 64 bit. Vì thế nên chúng ta cần những phương pháp mạnh hơn với ĐPT thấp hơn.

3. Những phép thử nền tảng

Thường thì những kiểm tra nguyên tố mạnh sẽ hoạt động trong thời gian `n - 1`5, đó là bởi vì hầu hết những phép thử nguyên tố đơn giản sau đều chạy trong thời gian ngắn nhất là `n - 1`5:

Nếu p là một số nguyên tố thì:

• `n - 1`7 (đây là nội dung của định lí Fermat nhỏ, ngoài ra số 2 có thể là một số khác không chia hết cho p)
• `n - 1`8 (với `n - 1`9 là số Fibonacci thứ `n`0 và `n`1 có dạng `n`2)

Tuy nhiên, chỉ đơn thuần sử dụng những phép thử trên sẽ không giúp chúng ta kết luận được số đang thử là số nguyên tố.

Ngoài ra còn phép thử: `n`3 khi và chỉ khi `n`1 nguyên tố. Đây là nội dung của định lí Wilson, nhưng việc tính toán biểu thức `n`5 sẽ có ĐPT lớn hơn `n - 1`5.

Trên thực tế, trong hầu hết trường hợp, chúng ta chỉ cần phép thử thứ nhất cho các kiểm tra "sừng sỏ" mình sẽ giới thiệu sau đây.

4. Những kiểm tra xác suất

Chúng được gọi là "xác suất" vì sau khi kiểm tra, chúng ta không thể thực sự chắc chắn liệu n có nguyên tố hay không như những phương pháp đơn giản trên. Tuy nhiên, chúng lại được dùng nhiều hơn những phương pháp đảm bảo độ chắc chắn vì tốc độ thực hiện của chúng.

Những số vượt qua kiểm tra xác suất mà trên thực tế không phải là số nguyên tố được gọi là những số "giả nguyên tố".

Kiểm tra Fermat

Đây là kiểm tra xác suất đơn giản nhất. Nó trực tiếp sử dụng định lí Fermat nhỏ:

Chọn số n`8 sao cho `n`9. Nếu `n`0 thì `n là hợp số. Ngược lại, n có thể là số nguyên tố.

Với n`3, dù 341 là hợp số (341 = 11 x 31), đẳng thức sau vẫn đúng: `n`4. Vì vậy, càng nhiều số `n`8 đúng với đẳng thức trên, khả năng `n là số nguyên tố càng tăng. Tuy nhiên, vẫn có những hợp số n thỏa mãn đẳng thức n`8 với mọi số `n`8 nguyên tố cùng nhau với `n, như số 561. Những số như vậy gọi là số Carmichael.

Kiểm tra Miller-Rabin

Đây là kiểm tra rườm rà hơn nhưng chắc chắn hơn kiểm tra Fermat, vì đây là kiểm tra số giả nguyên tố mạnh. Kiểm tra này hoạt động như sau:

Chọn 1 số n`8 bất kì nhỏ hơn `n. Giả sử `n`3 với `n`4 lẻ. Nếu:

• `n`5
• `n`6 (^ là kí hiệu phép lũy thừa, không phải phép XOR đâu)

thì n là hợp số. Ngược lại, n có thể là số nguyên tố.

Kiểm tra Solovay-Strassen

Kiểm tra này phức tạp hơn nhưng lại yếu hơn kiểm tra Miller-Rabin.

Chọn 1 số n`8 bất kì nhỏ hơn `n. Nếu thì n là hợp số. Ngược lại, n có thể là số nguyên tố. (vế phải là kí hiệu Jacobi)

Ngoài những kiểm tra xác suất phổ biến trên, còn những kiểm tra khác phức tạp hơn như kiểm tra Frobenius hay kiểm tra Baillie-PSW. Ta cũng có thể sử dụng đồng thời các kiểm tra trên để tăng tính chính xác của thuật toán. Ví dụ như kiểm tra Baillie-PSW sử dụng kiểm tra Miller-Rabin và kiểm tra xác suất Lucas.

Tạm kết

Trên đây là những phương pháp phổ biến để kiểm tra tính nguyên tố của một số. Mặc dù sử dụng chúng không thể giúp chúng ta tìm được số nguyên tố lớn nhất hiện nay, chúng có vẻ thừa đủ để hỗ trợ chúng ta trong những vấn đề lập trình hàng ngày.