Chuyên đề số nguyên tố - ôn thi hsg thành phố

CHUYÊN ĐỀ: SỐ NGUYÊN TỐ
ĐẶT VẤN ĐỀ
Số nguyên tố là một lĩnh vực Toán-Tin, có rất nhiều bài toán xử lí số nguyên tố. Đặc biệt là trong các cuộc thi tin học lập trình của thành phố và quốc gia, đó là một chủ đề hay và được ứng dụng nhiều. Vì lí do đó tôi xin trình bày chuyên đề về số nguyên tố để cùng chia sẻ và cùng đồng nghiệp xây dựng phương pháp giải cho một số dạng bài toán trong chuyên đề này.
NỘI DUNG
Khái niệm
Một số tự nhiên p (p>1) là số nguyên tố nếu p có đúng 2 ước số là 1 và p. Ví dụ các số nguyên: 2, 3, 5, 7, 11, 13 là các số nguyên tố.
Kiểm tra tính nguyên tố
Để kiểm tra số nguyên dương n (n>1) có là số nguyên tố không, ta kiểm tra xem có tồn tại một số nguyên k (k=2..n-1) mà p chia hết cho k thì p không phải là số nguyên tố, ngược lại là số nguyên tố.
Cài đặt
Function ngto(n:longint): Boolean;
Var i:longint;
Begin
if (n<1) then exit(false);
if (n<=3) then exit(true);
For i:=2 to n-1 do
If (n mod i = 0) then exit(false)
Else exit(true);
End;


Nhận xét: theo cách trên thì độ phức tạp về thời gian sẽ là O(n). Vậy ta có một cách cải tiến khác là chỉ cho i chạy từ 2 đến (n div 2), sẽ giảm độ phức tạp về O(n/2). Nhưng khi n là rất lớn thì cách này cũng không có ý nghĩa gì so với cách trên. Với độ phức tạp này thì máy tính sẽ phải thực hiện trong thời gian rất lâu (với tốc độ trung bình của một máy tính hiện nay thì một giây có thể xử lí khoảng 108 phép toán). Như vậy bài toán trên nếu n≤1010 phải mất khoảng thời gian là (1010/108) giây.
Vận dụng kiến thức toán học cho ta thấy khi n chia hết cho i thì cũng chia hết cho thương của phép chia n/i (ví dụ: 10 chia hết cho 2 thì cũng chia hết cho 5). Theo tính chất đó ta chỉ cần cho i chạy từ 2 đến phần nguyên căn bậc 2 của n. Thuật toán được cải tiến như sau:
Function ngto(n:longint): Boolean;
Var i:longint;
Begin
if (n<1) then exit(false);
if (n<=3) then exit(true);
For i:=2 to trunc(sqrt(n)) do
If (n mod i = 0) then exit(false)
Else exit(true);
End;

* Nhận xét độ phức tạp thời gian của thuật toán trên là O(
), với độ phức tạp này thì bài toán trên máy tính chi mất dưới 1s để giải quyết.
Một số dạng bài toán:
Bài toán 1: Cho dãy số a1,a2,…, an. (n<=1000; ai là số nguyên dương, ai<=109), hãy cho biết trong dãy có bao nhiêu số nguyên tố trong dãy?
* Input: tệp nguyento.inp gồm:
Dòng đầu tiên là số nguyên dương n
N dòng tiếp theo mỗi dòng là số nguyên dương ai
* Output: tệp nguyento.out gồm:
Số nguyên duy nhất là số các chữ số nguyên tố trong dãy.
* Nhận xét: với bài toán này, chỉ cần duyệt từ phần tử đầu tiên đến phần tử cuối cùng, gọi hàm kiểm tra nguyên tố cho từng phần tử, nếu đúng thì tăng biến đếm, nếu sai thì không tăng. Chương trình được viết như sau:
* Chương trình
program dem_nguyen_to;
const fi=`nguyento.inp`;
fo=`nguyento.out`;
var f1,f2:text;
dem,n:integer;
a:array[1..1000] of longint;

procedure doc;
var i:integer;
begin
assign(f1,fi);
reset(f1);
readln(f1,n);
for i:=1 to n do readln(f1,a[i]);
close(f1);
end;

Function ngto(n:longint): Boolean;
Var i:longint;
Begin
if (n<1) then exit(false);
if (n<=3) then exit(true);
For i:=2 to trunc(sqrt(n