Sáng kiến kiến nghiệm - Chuyên đề Số nguyên tố trong công tác bồi dưỡng HSG môn Tin học - Đỗ Xuân Quyền

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)) do
 	 If (n mod i = 0) then exit(false)
 Else exit(true);
End;
procedure ghi;
begin
 assign(f2,fo);
 rewrite(f2);
 writeln(f2,dem);
 close(f2);
end;
Procedure xuli;
var i:integer;
begin
 dem:=0;
 for i:=1 to n do
 if ngto(a[i]) then inc(dem);
 ghi;
end;
BEGIN
 doc;
 xuli;
END.
Bài toán 2: Cho dãy số a1,a2,, an. (n<=106; ai là số nguyên dương, ai<=109), hãy cho biết trong đoạn [l,r] của dãy có bao nhiêu số nguyên tố (1<=l<=r<=106). Yêu cầu bài thực hiện trong 1 giâ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
Dòng cuối cùng là 2 số l và r.
* 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 độ phức tạp đã tăng lên (n<=106), nếu ta giải quyết bài toán với thuật toán 2 thì độ phức tạp thời gian sẽ tăng thành O(106*), đồng nghĩa với thời gian xử lí sẽ lớn hơn 1 giây. Trong tình huống này ta sẽ phải sử dụng sàng nguyên tố Eratosthene, để liệt kê được các số nguyên tố nhanh, tuy nhiên nhược điểm của phương pháp này là tốn nhiều bộ nhớ. Thuật toán như sau:
* Thuật toán: 
B1: xóa 1 khỏi tập các số nguyên tố
B2: Xét I = 2 đến trunc(sqrt(n)) //phần nguyên căn bậc 2 của n
	Nếu I là số nguyên tố (f[i]=true) thì các bội của I là (j:=i*i; j:=j+i) không là nguyên tố (f[j]=false).
B3: Các số còn lại trên dãy từ 1 đến n nhận giá trị true là số nguyên tố.
* Chương trình thực hiện như sau:
program dem_nguyen_to;
const Nmax=100000000;
 fi='nguyento.inp';
 fo='nguyento.out';
var f1,f2:text;
 dem,n,l,r:integer;
 a:array[1..1000000] of longint;
 f:array[1..Nmax] of boolean;
procedure doc;
var i:integer;
begin
 assign(f1,fi);
 reset(f1);
 readln(f1,n);
 for i:=1 to n do readln(f1,a[i]);
 readln(f1,l,r);
 close(f1);
end;
procedure sang_estr;
var i,j:longint;
begin
 fillchar(f,sizeof(f),true);
 f[1]:=false;
 for i:=2 to trunc(sqrt(n)) do
 if f[i] then
 begin
 j:=i*i;
 while j<=n do
 begin
 f[j]:=false;
 j:=j+i;
 end;
 end;
end;
procedure ghi;
begin
 assign(f2,fo);
 rewrite(f2);
 writeln(f2,dem);
 close(f2);
end;
procedure xuli;
var i:longint;
begin
 dem:=0;
 for i:=l to r do
 if f[a[i]] then inc(dem);
 ghi;
end;
BEGIN
 doc;
 sang_estr;
 xuli;
END.
ỨNG DỤNG
( Giải các bài toán về số nguyên tố trong một số đề thi chọn HSG thành phố).
Bài 1: (Bài 1-Đề thi chọn học sinh giỏi thành phố năm học 2009-2010 bảng A và B).
Cho số nguyên dương N (2≤N≤1010)
Yêu cầu:
Phân tích N thành các thừa số nguyên tố dưới dạng N=a*b*c* (với a,b,c là các số nguyên tố)?
Giả sử: cho N = 81
- Vì N=81=34 nên biểu diễn dưới dạng tích các thừa số nguyên tố: 3*3*3*3
* Dữ liệu vào: cho trong tệp bai1.inp gồm
- dòng duy nhất chứa số N
* Dữ liệu ra: Ghi ra tệp bai1.out gồm các thừa số được phân tích cách nhau dấu cách.
Ví dụ:
Bai1.inp
Bai1.out
1296
2 2 2 2 3 3 3 3
* Ý tưởng: ta sẽ viết một hàm kiểm tra số nguyên tố i (bắt đầu với i=2) để làm số chia cho phép chia n div i, lặp cho đến khi n là số nguyên tố.
* Thuật toán
B1: Nếu N là số nguyên tố thông báo kết quả và kết thúc
B2: i=2
B3: Khi n chưa là nguyên tố thì còn lặp 
B3.1. nếu i là nguyên tố thì 
Nếu n mod I =0 thì 
thêm I vào danh sách
n=n div i
nếu n là nguyên tố thì dừng lặp, ngược lại tăng I và chuyển đến B3.1
Nếu n mod I 0 thì tăng I và quay lại B3.1
B3.2. nếu I không phải là nguyên tố thì tăng I và quay lại B3.1
	B4. Thông báo kết quả là tích dãy I và n
* Chương trình
Program bai1_2009_2010;
const fi='bai1.inp';
 fo='bai1.out';
var f:array[1..1000] of longint;
 n:longint;
 k:integer;
 f1,f2:text;
procedure doc;
begin
 assign(f1,fi);
 reset(f1);
 readln(f1,n);
 close(f1);
end;
function nto(x:longint):boolean;
var i:longint;
begin
 if x<=1 then exit(false);
 for i:=2 to trunc(sqrt(x)) do
 if x mod i = 0 then exit(false);
 exit(true);
end;
procedure xuli;
var i:longint;
begin
 k:=0;
 if nto(n) then
 begin
 inc(k);
 f[k]:=n;
 end
 else
 begin
 i:=2;
 while not(nto(n)) do
 begin
 while not(nto(i)) do inc(i);
 while n mod i = 0 do
 begin
 inc(k);
 f[k]:=i;
 n:=n div i;
 if n=1 then exit;
 end;
 inc(i);
 end;
 inc(k);
 f[k]:=n;
 end;
end;
procedure ghi;
var i:integer;
begin
 assign(f2,fo);
 rewrite(f2);
 for i:=1 to k do write(f2,f[i],' ');
 close(f2);
end;
BEGIN
 doc;
 xuli;
 ghi;
END.
Bài 2: (Bài 2.a-Đề thi chọn học sinh giỏi thành phố năm học 2008-2009)
Trong một phân xưởng săn xuất, để hoàn thành được một sản phẩm, người quản đốc phải sử dụng n công nhân để gia công n chi tiết. Biết rằng công sức để gia công một chi tiết của mỗi công nhân là khác nhau. Người ta sử dụng một mảng hai chiều C gồm n hàng và n cột biểu diễn chi phí gian công của công nhân cho từng chi tiết cụ thể, trong đó giá trị c[i,j] là số công bỏ ra của công nhân tứ I gia công chi tiết j (1≤ c[i,j]≤20000).
Yêu cầu:
- Kiểm tra xem với mỗi chi tiết nếu tất cả các công nhân đề tham gia gia công thì tổng số công bỏ ra của mọi nguowif cho chi tiết đó có là số siêu nguyên tố không?
(ghi chú: số siêu nguyên tố là số nguyên tố mà khi bỏ một số tùy ý các chữ số bên phải của nó thì phần còn lại vẫn tạo thành một số nguyên tố: ví dụ 537 là một số siêu nguyên tố có 3 chữ số vì 53, 5 là các số nguyên tố).
* Dữ liệu vào: cho trong tệp bai2.inp
- Dòng đầu tiên là số nguyên n (1≤n≤20) là số lượng công nhân và số chi tiết.
- Trong n dòng tiếp theo mỗi dòng biểu diễn n giá trị c[i,j] được ngăn cách nhau bởi dấu cách. Thể hiện số công bỏ ra của công nhân thứ I gia công cho n chi tiết tương ứng.
* Kết quả: đưa ra tệp văn bản bai2.out
- gồm 1 dòng ghi số 1 hoặc 0 được ngăn cách nhau bởi dấu cách thể hiện tổng số công bỏ ra của tất cả các công nhân khi gia công mỗi chi tiết tương ứng có hoặc không là số siêu nguyên tố.
Ví dụ:
Bai2.inp
Bai2.out
3
4 5 7
3 6 8
7 8 8
0 0 1
Giải thích:
- Tổng số công của chi tiết số 1 = 14: không phải số siêu nguyên tố (ghi 0)
- Tổng số công của chi tiết số 2 =19: không phải số siêu nguyên tố(ghi 0)
- Tổng số công của chi tiết số 3=23: là số siêu nguyên tố (ghi 1).
Nhận xét: 
	Trước tiên phải xây dựng một hàm kiểm tra số siêu nguyên tố, trong đó có sử dụng hàm kiểm tra nguyên tố.
	Tính tổng từng cột và kiểm tra tổng đó có là siêu nguyên tố không.
* Chương trình
program bai2_08_09;
const fi='bai2.inp';
 fo='bai2.out';
var f1,f2:text;
 c:array[1..20,1..20] of integer;
 n:byte;
procedure modoc;
var i,j:byte;
begin
 assign(f1,fi);
 reset(f1);
 readln(f1,n);
 for i:=1 to n do
 begin
 for j:=1 to n do read(f1,c[i,j]);
 readln(f1);
 end;
 close(f1);
 assign(f2,fo);
 rewrite(f2);
end;
function nto(x:longint):boolean;
var i:integer;
begin
 if x<=1 then exit(false);
 for i:=2 to trunc(sqrt(x)) do
 if x mod i = 0 then exit(false);
 exit(true);
end;
function snto(x:longint):boolean;
begin
 if nto(x) and (x div 10 =0) then exit(true);
 while x div 10 0 do
 if nto(x) then x:=x div 10
 else exit(false);
 if nto(x) then exit(true)
 else exit(false);
end;
procedure xuli;
var i,j:byte;
 t:longint;
begin
 for j:=1 to n do
 begin
 t:=0;
 for i:=1 to n do
 t:=t+c[i,j];
 if snto(t) then write(f2,1,' ')
 else write(f2,0,' ');
 end;
 close(f2);
end;
BEGIN
 modoc;
 xuli;
END.
Bài 3: (bài 3- Đề thi chọn học sinh giỏi thành phố bảng A năm 2014-2015)
Bạn được cho biết số N và dãy A=(a1,a2,..,an). Để tránh việc phải đọc một lượng dữ liệu quá lơn, dãy A sẽ được cho bởi 3 số nguyên dương p,q,m, trong đó mỗi phần tử ai được xác định bởi công thức:
	ai=(p*i) mod m + q (1≤ i ≤ n)
Có T câu hỏi dạng u,v (u≤v) yêu cầu cho biết trong đoạn au, au+1,,av có bao nhiêu số nguyên tố?
* Dữ liệu vào từ file văn bản bai3.inp
- Dòng 1 chứa 2 số nguyên dương n và T
- Dòng 2 chứa 3 số nguyên dương p,q,m xác định dãy A (p,q,m≤106);
- T dòng tiếp theo, dòng thứ I chứa 2 số u,v tương ứng với câu hỏi I là trong đoạn [u,v] có bao nhiêu số nguyên tố?
* Kết quả ghi ra file văn bản bai3.out
- T dòng, dòng thứ I là câu trả lời của câu hỏi thứ i
Ví dụ:
Bai3.inp
Bai3.out
Giải thích
5 4
2 1 9
1 3
2 4
3 5
4 4
3
2
2
0
Dãy A=(3,5,7,9,2)
Đoạn [1,3] là (3,5,7) có 3 số nguyên tố
Đoạn [2,,4] là (5,7,9) có 2 số nguyên tố
Chú ý: (chương trình chạy trong 1 giây)
40% điểm ứng với các test có n≤1000, T=1
40% điểm ứng với các test có n≤1000, T≤1000
20% điểm ứng với các test có n≤1000, T≤10000
* Nhận xét: với bài toán này nếu chỉ viết hàm kiểm tra nguyên tố thì độ phức tạp tối đa là O(104 * 103 * 103), chương trình sẽ chạy khoảng 102s. Vì vậy ta phải sử dụng sàng nguyên tố Eratosthene để giải quyết bài toán này.
* Chương trình
CONST
 tfi = 'BAI3.INP';
 tfo = 'BAI3.OUT';
TYPE
 arr1 = array[0..1000] of longint;
 arr2 = array[1..2000000] of longint;
VAR
 sum : arr1;
 Prime : arr2;
 N,m,p,q,kq,t : longint;
 fi,fo : text;
(*--------------------------------*)
procedure sang_nguyen_to;
 Var
 i,j : longint;
 Begin
 Prime[1] := 1;
 For i := 2 to trunc(sqrt(2000000)) do
 if prime[i] = 0 then
 begin
 j := i*i;
 while j <=1000000 do
 begin
 prime[j] := 1;
 j := j + i;
 end;
 end;
 end;
(*--------------------------------*)
Procedure xuli;
 Var
 i,x,u,v : longint;
 Begin
 sum[0] := 0;
 assign(fi,tfi); reset(fi);
 assign(fo,tfo); rewrite(fo);
 readln(fi,n,t);
 readln(fi,p,q,m);
 for i := 1 to n do
 begin
 x := (p*i) mod m + q;
 if prime[x]=0 then sum[i] := sum[i-1] + 1
 else sum[i] := sum[i-1];
 end;
 for i := 1 to t do
 begin
 readln(fi,u,v);
 writeln(fo,sum[v]- sum[u-1]);
 end;
 close(fo);
 close(fi);
 End;
(*--------------------------------*)
(*--------------------------------*)
BEGIN
 sang_nguyen_to;
 xuli;
END.
KẾT LUẬN
	Trên đây là chuyên đề về xử lí số nguyên tố trong lập trình mà bản thân tôi đã tích lũy được trong quá trình làm việc, khi giảng dạy các lớp và đặc biệt là bồi dưỡng đội tuyển học sinh giỏi đã gây được hứng thú cho các em và mang lại hiệu quả tốt. Nhưng khi viết thành chuyên đề chắc chắn nội dung không thể tránh khỏi thiếu sót mong các đồng chí trong tổ góp ý, bổ sung để chuyên đề hoàn thiện hơn.
	Tôi xin trân trọng cảm ơn!
Người viết
 Đỗ Xuân Quyền