SKKN Tính nguyên tố của một số nguyên và sử dụng tính nguyên tố để giải quyết một số bài toán

MỤC LỤC
	 	 TRANG
1. MỞ ĐẦU	2
 Lý do chọn đề tài	2
 Mục đích nghiên cứu	2
 Đối tượng nghiên cứu	3
 Phương pháp nghiên cứu	3
2. NỘI DUNG CỦA SÁNG KIẾN KINH NGHIỆM	3
 Cơ sở lý luận của sáng kiến kinh nghiệm	3
Thực trạng vấn đề trước khi áp dụng sáng kiến kinh nghiệm	3
Các sáng kiến kinh nghiệm hoặc các giải pháp đã sử dụng 	
để giải quyết vấn đề	4
2.3.1 Kiểm tra tính nguyên tố của một số nguyên dương.......4
2.3.2 Phân tích một số thành tích các thừa số nguyên tố ...6
2.3.3 Một số ví dụ7
Hiệu quả của sáng kiến kinh nghiệm đối với hoạt động 	
giáo dục, với bản thân, đồng nghiệp và nhà trường.	17
3. KẾT LUẬN, KIẾN NGHỊ	17
Kết luận	17
Kiến nghị	17
MỞ ĐẦU
Lý do chọn đề tài:
Công nghệ thông tin của nước ta hiện nay đang rất phát triển đưa ra nhiều triển vọng cho tất cả các ngành trong việc tin học hoá xã hội. Công nghệ tông tin có ý nghĩa rất quan trọng đối với rất nhiều lĩnh vực của đời sống, máy tính hiện nay cũng không còn xa lạ đối với mọi người. Trong ngành giáo dục hiện nay cũng là một ngành đang đưa công nghệ thông tin vào ứng dụng trong việc dạy và học.
Thực hiện Nghị quyết số 26/NQ-CP ngày 15/4/2015 của Chính phủ ban hành Chương trình hành động thực hiện Nghị quyết số 36-NQ/TW ngày 01/7/2014 của Bộ Chính trị Ban Chấp hành Trung ương Đảng Cộng sản Việt Nam về đẩy mạnh ứng dụng, phát triển công nghệ thông tin (CNTT) đáp ứng yêu cầu phát triển bền vững và hội nhập quốc tế; thực hiện Quyết định số 1755/QĐ-TTg ngày 22/9/2010 của Thủ tướng Chính phủ phê duyệt Đề án “Đưa Việt Nam sớm trở thành nước mạnh về công nghệ thông tin và truyền thông”; thực hiện Chỉ thị số 16/CT-TTg ngày 04/5/2017 của Thủ tướng Chính phủ về việc tăng cường năng lực tiếp cận cuộc Cách mạng công nghiệp lần thứ 4, Bộ Giáo dục và Đào tạo hướng dẫn cơ chế đặc thù đào tạo các ngành thuộc lĩnh vực CNTT trình độ đại học giai đoạn 2017-2020 để đáp ứng nhu cầu của thị trường lao động và hội nhập quốc tế.
Học sinh THPT là nguồn lao động trẻ có thể sử dụng ngay sau khi tốt nghiệp do vậy việc được tiếp cận công nghệ thông tin từ trong nhà trường phổ thông sẽ giúp cho học sinh có thể tự tin hơn trong công việc. Việc đào tạo học sinh có nền tảng lập trình cơ bản và có đam mê lập trình có vai trò quan trọng trong sự phát triển sau này của các em. Thông qua việc dạy đội tuyển học sinh giỏi, dạy những lớp mũi nhọn nhiều năm để học sinh yêu thích lập trình tôi rút ra những kinh nghiệm sau:
+ Tạo sự đam mê lập trình và đọc sách.
+ Vận dụng các kiến thức đã học để giải các bài toán thực tế
+ Hình thành và phát triển tư duy logic
+ Hình thành các bước để giải quyết vấn đề nêu ra
+ Dạy học thông qua các chuyên đề độc lập hay liên hệ giữa toán học và tin học để giải quyết các bài toán.
Trong quá trình dạy học sinh và đứng đội tuyển học sinh giỏi tôi thấy rằng nhiều bài toán sẽ được giả quyết nhanh nếu chúng ta biết tính chất của các số và áp dụng hợp lý. Với những lý do trên tôi chọn đề tài về “Tính nguyên tố của một số nguyên và sử dụng tính nguyên tố để giải quyết một số bài toán” 
Mục đích nghiên cứu.
Đưa ra tính nguyên tố của một số nguyên, các thuật toán cơ bản liên quan đến số nguyên tố. Đưa ra một số bài toán có sử dụng tính nguyên tố của một số nguyên để giải quyết. Qua các bài toán này giúp học sinh yêu thích việc tư duy logic và thấy được sự kỳ diệu của các con số. 
 Đối tượng nghiên cứu.
Học sinh khối 11 và đội tuyển học sinh giỏi trường THPT Nông Cống 1.
 Phương pháp nghiên cứu
Phương pháp phân tích thuật toán, kiểm tra đánh giá năng lực học sinh, phát triển tư duy logic. Một số tài liệu tham khảo và tìm kiếm thông tin trên internet.
Nội dung sáng kiến
2.1. Cơ sở lí luận của sáng kiến kinh nghiệm.
- Nghị quyết số 44/NQ-CP, ngày 09/6/2014 Ban hành chương trình hành động của chính phủ thực hiện nghị quyết số 29-NQ/TW ngày 04/11/2013 Hội nghị lần thứ 8 Ban chấp hành Trung ương khóa XI về đổi mới căn bản, toàn diện giáo dục và đào tạo, đáp ứng yêu cầu công nghiệp hóa trong điều kiện kinh tế thị trường định hướng xã hội chủ nghĩa và hội nhập quốc tế xác định “Đổi mới hình thức, phương pháp thi, kiểm tra và đánh giá kết quả giáo dục theo hướng đánh giá năng lực của người học; kết hợp đánh giá cả quá trình với đánh giá cuối kỳ học, cuối năm học theo mô hình của các nước có nền giáo dục phát triển”.
- Luật Giáo dục số 38/2005/QH11, Điều 28 quy định: “Phương pháp giáo dục phổ thông phải phát huy tính tích cực, tự giác, chủ động, sáng tạo cảu học sinh; phù hợp với đặc điểm của từng lớp học, môn học; bồi dưỡng phương pháp tự học, khả năng làm việc theo nhóm; rèn luyện kỹ năng kiến thức vào thực tiễn; tác động đến tình cảm, đem lại niềm vui, hứng thú học tập cho học sinh”
+ Ngoài việc tạo điều kiện cho học sinh chiếm lĩnh những tri thức và kỷ năng Tin học cần thiết, Tin học còn có tác dụng phát triển năng lực trí tuệ chung như: phân tích, tổng hợp, trừu tượng hoá, khái quát hoárèn luyện những đức tính, phẩm chất của người lao động mới. Học sinh sẽ thấy rõ hiệu quả mạnh mẽ của công nghệ thông tin và nhận thức cần có.
2.2. Thực trạng vấn đề trước khi áp dụng sáng kiến kinh nghiệm.
Sự quan trọng của CNTT trong xã hội hiện nay ai cũng biết nhưng để được sự quan tâm của các em học sinh, phụ huynh, nhà trường là cả một khó khăn. 
Quá trình thực hiện đề tài tại trường THPT Nông Cống 1 tôi có một số thuận lợi và khó khăn sau:
2.2.1. Thuận lợi:
* Nhà trường:
- Ban giám hiệu nhà trường luôn đạo điều kiện tốt nhất để giáo viên và học sinh học tập.
- Nhà trường đã đầu tư một phòng thực hành tin với 24 máy tính xách tay để cho các em đam mê lập trình và đội tuyển học sinh giỏi học tập.
- Được sự giúp đỡ, tạo điều kiện của tổ nhóm chuyên môn Toán – Tin.
* Học sinh:
Nhiều học sinh đã thấy được tiềm năng phát triển của ngành CNTT trong tương lai, qua đó có ý thức và định hướng về nghề CNTT.
2.2.2. Khó khăn:
* Nhà trường:
Nhà trường đã tạo điều kiện tối đa nhưng vì nhiều lý do nên cơ sở vật chất để có thể học tốt môn tin học chưa đáp ứng được nhu cầu của học sinh.
* Giáo viên:
Tài liệu của môn tin học trong nhà trường khá ít do đó gây khó khăn cho việc nâng cao trình độ.
Đời sống giáo viên còn nhiều khó khăn nên việc tập trung tối đa cho môn học cũng bị ảnh hưởng.
* Học sinh:
Lập trình có đặc trưng riêng so với các môn học khác nên sự tiếp cận của học sinh khá khó khăn.
Nhiều học sinh yêu thích và đam mê lập trình nhưng điều kiện kinh tế gia đình chưa đủ để các em có thể chuyên tâm học tập.
Tư tưởng học để thi đại học vẫn còn nặng trong học sinh nên thời gian học dành cho sự đam mê môn tin học là không đủ.
Các sáng kiến kinh nghiệm hoặc các giải pháp đã sử dụng để giải quyết vấn đề.
	Khái niệm số nguyên tố (prime number): Số nguyên tố là số nguyên dương chỉ chia hết cho 1 và chính nó. Từ đó suy ra số một không phải là một số nguyên tố (có rất nhiều em mới học lập trình nhầm số 1 là số nguyên tố). Một kết quả khác cũng không kém quan trọng được rút ra đó là số 2 là số nguyên tố đầu tiên (nhỏ nhất) và cũng là số số nguyên tố chẵn duy nhất.
 Kiểm tra tính nguyên tố của số nguyên dương.
Kiểm tra tính nguyên tố của một số nguyên dương
	Để kiểm tra một số nguyên dương N có là số nguyên tố hay không ta kiểm tra xem N có tồn tại số nguyên k sao cho k là ước của N hay không? Nếu tồn tại số nguyên k thì N không phải số nguyên tố ngược lại N là số nguyên tố.
	Ta có thể tìm số k bằng cách lấy N chia cho các số từ 2 cho đến N-1. Nếu N không phải số nguyên tố thì N có thể phân tách N= k1 x k2 với 2≤k1≤k2<N-1 vì k1×k1≤k1×k2=N nên k1≤N. Do đó ta chỉ cần kiểm tra k từ 2 đến N mà không cần kiểm tra từ 2 đến N-1.
Ta có đoạn chương trình sau:
function ngto(n:longint):boolean; 
var k :longint;
	begin
	if n=1 then exit(false);
	for k:=2 to trunc(sqrt(n)) do
	if (n mod k=0) then exit(false); exit(true);
	 	end;
	Hàm ngto(n) kiểm tra lần lượt các nguyên trong đoạn 2,N để giảm thiểu số cần kiểm tra ta có nhận xét: Để kiểm tra số N là số nguyên tố hay không ta kiểm tra xem có tồn tại số nguyên tố k (2≤k≤N) mà k là ước của N. Nếu tồn tại k thì N không phải số nguyên tố ngược lại thì N là số nguyên tố. Để tránh việc phải kiểm tra k có phải là số nguyên tố hay không ta có thể dựa vào một trong hai tính chất đơn giản của số nguyên tố sau:
	1. Trừ 2 các số nguyên tố đều lẻ.
	2. Trừ số 2, 3 các số nguyên tố có dạng 6k±1
	Do vậy kiểm tra số N có phải là số nguyên tố hay không ta chỉ cần kiểm tra xem N có chia hết cho số 2, số 3 và các số có dạng 6k±1 trong khoảng 5, N
Ta có đoạn chương trình sau:
function ngto(n:longint):boolean; 
var k,sqrt_n:longint;
begin
	if (n=2)or(n=3) then exit(true);
if (n=1) or (n mod 2=0) or (n mod 3=0) then exit(false); sqrt_n:=trunc(sqrt(n));
	k:=-1;
	repeat
	inc(k,6);
	if (n mod k=0)or(n mod (k+2)=0) then break;
	until k>sqrt_n;
	exit(k>sqrt_n);
	end;
Liệt kê các số nguyên tố trong đoạn 1, N
Ta có thể dùng hàm ngto(n) để kiểm tra lần lượt các số trong đoạn 1, N
Đoạn chương trình:
	For i := 2 to N do
	 If ngto(i) then write(i);
Cách này là cách đơn giản nhưng chạy chậm nên ta cải tiến bằng cách sử dụng sàng nguyên tố. Cách làm được thực hiện như sau:
	Trước tiên xóa số 1 ra khỏi tập số nguyên tố. Số tiếp theo là số 2 là số nguyên tố ta xóa tất cả các số là bội của 2. Số đầu tiên sau số 2 không bị xóa là số 3 ta lại xóa tất cả các số là bội của 3thuật toán tiếp tục đến khi gặp số nguyên tố lớn hơn N thì dừng lại. Các số chưa bị xóa là các số nguyên tố.
Ta có đoạn chương trình sau:
Const max=10000;
Procedure sangngto(N:longint);
Var i,j: longint
 A: array[1..max] of byte;
Begin 
	fillchar(a,sizeof(a),0); 
	for i:=2 to trunc(sqrt(N)) do
	 if a[i]=0 then 
	begin
	j:=i*i; 
	while j<=N do
	begin
	a[j]:=1; 
	j:=j+i;
	end;
	end;
	for i:=2 to N do
	if a[i]=0 then writeln(i);
end;
Phân tích một số thành tích các thừa số nguyên tố.
	Theo định lý cơ bản của số học: Mọi số nguyên dương đều có thể biểu diễn duy nhất thành tích của các số nguyên tố.
	Hệ quả: Mọi số tự nhiên N>1 đều có thể biễu diễn duy nhất dưới dạng chuẩn tắc
 N=p1k1×p2k2××psks trong đó ki là số nguyên dương và pi là các số nguyên tố với p1<p2<<ps .
	Ta có bài toán: Cho một số nguyên dương N (2<N<109) hãy phân tích N thành tích các thừa số nguyên tố. 
Ví dụ:
Bai.inp
Bai.out
168
2^3
3^1
7^1
Thuật toán:
	Dùng một mảng để lưu lũy thừa. Mảng này có giá trị các phần tử ban đầu đều bằng 0. Cho i chạy từ 2 đến N Nếu n chia hết cho i thì tăng a[i] lên 1.
Khi in kiểm tra: Nếu a[i] >0 thì in i^a[i].
Chương trình
Const fi='bai.inp';
 fo='bai.out';
Var n, i,s,j : longint;
 a:array[2..100000]of longint;
	f1,f2:text; 
BEGIN
 Assign(f1,fi);Reset(f1);
 Assign(f2,fo);Rewrite(f2);
 Read(f1,n);
 i:=2;a[2]:=0;
 While n1 do
 begin
 While n mod i0 do
 begin
 i:=i+1;
 a[i]:=0;
 end;
 a[i]:=a[i]+1;
 n:=n div i;
 end;
 For j:=2 to i do
 If a[j]>0 then writeln(f2,j,'^',a[j]);
Close(f1); 
Close(f2);
END.
	Khi N được phân tích thành thừa số nguyên tố như sau:
	 N=p1k1×p2k2××psks
Ta có các kết luận sau:
	1. Số các ước của N là: k1+1×k2+1××(ks+1)
	2. Tổng các ước của một số
=(p1k1-1)p1-1×(p2k2-1)p2-1××(psks-1)ps-1
Một số ví dụ.
	Dựa vào tính chất nguyên tố của một số nguyên dương và việc phân tích một số thành tích của các thừa số nguyên tố tối có một sô bài tập sau:
Bài toán 1: Số gần nguyên tố
	Chúng ta đều biết số nguyên tố là số nguyên dương mà chỉ có duy nhất 2 ước phân biệt. Mạnh luôn thích những cái đặc biệt và mới mẻ, và anh ra đưa ra 1 định nghĩa mới “Số gần nguyên tố” – là các số nguyên dương mà có đúng 3 ước phân biệt.
Yêu cầu: Cho 1 mảng có n phần tử, hãy cho biết có bao nhiêu phần tử trong mảng là số gần nguyên tố.
Dữ liệu vào: Từ file văn bản BAI1.INP
- Dòng đầu tiên: Số tự nhiên n (1 ≤ n ≤ 106) là số phần tử của mảng.
- Dòng tiếp theo: Gồm n số nguyên dương x[i] (1 ≤ x[i] ≤ 109).
Dữ liệu ra: Ghi ra file văn bản BAI1.OUT: Số phần tử trong mảng là số gần nguyên tố.
Ví dụ:
BAI1.INP
BAI1.OUT
3
4 5 6
1
Thuật toán:
	Đối với bài toán này nếu chúng ta duyệt lần lượt để tìm các ước của X thì sẽ rất chậm và không đủ thời gian theo yêu cầu. Do vậy ta thấy rằng nếu X mà được phân tích thành tích các thừa số nguyên tố X=p1k1×p2k2××psks thì tổng các ước là k1+1×k2+1××(ks+1). Theo đề bài thì số gần nguyên tố chỉ có đúng 3 ước do đó X chỉ có thể phân tích thành X=p12.
	Vậy X là số gần nguyên tố thì X phải là một số chính phương.
Chương trình:
var f1,f2:text;
 i,j,d,kq,n: longint;
function ngto(k:longint):boolean;
var j1:longint;
 kt:boolean;
begin
 j1:=2;kt:=false;
 if k>1 then
 begin
 while (j10) do inc(j1);
 if j1> sqrt(k) then kt:=true;
 end;
 ngto:=kt;
end;
begin
assign(f1,'bai1.inp'); reset(f1);
assign(f2,'bai1.out'); rewrite(f2);
readln(f1,n);kq:=0;
for j:=1 to n do
 begin
 read(f1,i);
 d:=trunc(sqrt(i));
 if (sqr(d)=i) and ngto(d) then inc(kq);
 end;
write(f2,kq);
close(f1);
close(f2);
end.
Bài toán 2: Phân tích
	Phân tích N! thành tích của các thừa số nguyên tố
Ví dụ: 15! = 211.36.53.72.11.13.
Thuật toán:
	Ta sẽ tìm cách phân tích n! ra thừa số nguyên tố. Các ước số nguyên tố của n! chỉ nằm trong phạm vi từ 2 đến n, do đó ta duyệt qua tất cả các số nguyên tố trong phạm vi này. Với số nguyên tố p, số mũ của nó trong biểu diễn nguyên tố của n! bằng công thức:
=np+np2+np3+
	Trong đó [n/p] ký hiệu phần nguyên của n/p, nói cách khác trong ngôn ngữ Pascal [n/p] bằng n div p. Công thức trên được giải thích như sau: [n/p] là số lượng số từ 1 đến n chia hết cho p, [n/p2] là số lượng số từ 1 đến n chia hết cho p2,... mỗi số này đều đóng góp một thừa số nguyên tố p phân biệt cho n!.
Ví dụ, với N = 15, p = 2 và kí hiệu : là phép chia nguyên, ta tính được 
15 : 2 = 7; 7 : 2 = 3; 3 : 2 = 1; 1 : 2 = 0. Do đó k = 7+3+1+0 = 11. 
Với N=15, p = 5 ta tính được 15 : 5 = 3; 3 : 5 = 0. Do đó k = 3+0 = 3.
Với N=15, p = 7 ta tính được 15 : 7 = 2; 2 :7 = 0. Do đó k = 2+0 = 2.
Với N=15, p = 11 ta tính được 15 : 11 = 1; 1 : 5 = 0. Do đó k = 1+0 = 1.
Với N=15, p = 13 ta tính được 15 : 13 = 1; 1 : 5 = 0. Do đó k = 1+0 = 3.
Như vậy 15! = 211.53.72.11.13.
Chương trình:
function ngto(n: longint): boolean;
var i: longint;
begin
 nguyento:=false;
 for i:=2 to trunc(sqrt(n)) do
 if n mod i = 0 then exit;
 ngto:=true;
end;
var
 n,i,j,a: longint;
begin
 readln(n);
 for i:=2 to n do if ngto(i) then
 begin
 a:=0;
 j:=i;
 while (j<=n) do
 begin
 a:=a+n div j;
 j:=j*i;
 end;
 write(i,'^',a,'.');
 end;
 readln
end.
Bài toán 3: SỐ ƯỚC
	Cho số nguyên dương N. Giai thừa của N, kí hiệu là N!, là tích của các số tự nhiên từ 1 đến N. Gọi T là số lượng ước lớn hơn 1 của N!. Ví dụ với N = 4, ta có 4! = 24. Như vậy 4! có 7 ước lớn hơn 1 là: 2, 3, 4, 6, 8, 12, 24.
Yêu cầu: Cho N, hãy xác định T.
Dữ liệu: Vào từ file văn bản SOUOC.INP trong đó chứa duy nhất số N (N <45, trong đó 50% số test có N <20).
Kết quả: Ghi ra file văn bản SOUOC.OUT số T tìm được.
Ví dụ: 
SOUOC.INP
SOUOC.OUT
4
7
Thuật toán: 
	Tương tự thuật toán bài trên.
Chương trình
function ngto(n: longint): boolean;
var i: longint;
begin
 nguyento:=false;
 for i:=2 to trunc(sqrt(n)) do
 if n mod i = 0 then exit;
 ngto:=true;
end;
var
 n,i,j,a,d: longint;
 f1,f2:text;
begin
 assign(f1,'souoc.inp'); reset(f1);readln(f1,n);
 assign(f2,'souoc.out'); rewrite(f2);
 d:=1;
 for i:=2 to n do if ngto(i) then
 begin
 a:=0;
 j:=i;
 while (j<=n) do
 begin
 a:=a+n div j;
 j:=j*i;
 end;
 d:=d*(a+1);
 	 end;
 writeln(f2,d-1);
Close(f1);
Close(f2);
	end.
Bài toán 4: Số chữ số 0 tận cùng.
	Cho N giai thừa. Hãy cho biết N! có tận cùng bao nhiêu chữ số 0.
Thuật toán:
	Tương tự thuật toán của bài 2. Tuy nhiên khi phân tích N! ra tích của các thừa số nguyên tố ta chỉ quan tâm đến 5p mà thôi. Số chữ số 0 tận cùng của N! chính là số mũ của số 5 trong phân tích.
	Ví dụ: 15!= 211.53.72.11.13. thì số chữ số 0 tận cùng bằng 3.
Đoạn chương trình:
Function tc(N:longint): longint; 
Var a, j: byte;
Begin 
 j:=5;
 while (j<=n) do
 begin
 a:=a+n div j;
 j:=j*5;
 end;
 tc:=a;
 	 end;
Bài toán 5: Không chứa chính phương
	Một số nguyên gọi là không chứa chính phương nếu nó không chia hết cho bất ký số nguyên nào dạng x2 với x > 1.
Yêu cầu: Cho số nguyên n (1 ≤ n ≤ 1013). Hãy tìm ước lớn nhất không chứa chính phương của n. Lưu ý là 1 và n cũng là ước của n.
Dữ liệu vào: Vào từ file văn bản CP.INP gồm nhiều tests, mỗi test cho trên một dòng chứa số nguyên n.
Dữ liệu ra: Đưa ra file văn bản CP.OUT, kết quả mỗi test đưa ra trên một dòng.
CP.INP
CP.OUT
9
20
3
10
Thuật toán:
	- Nếu làm bài toán này theo đúng định nghĩa của bài đưa ra (hay làm theo cách tự nhiên) thì chỉ qua được những test nhỏ.
	- Để giải quyết triệt để bài toán tìm ước không chứa chính phương của N ta phân tích N thành tích các thừa số nguyên tố, ước lớn nhất thỏa mãn yêu cầu của bài là tích các thừa số nguyên tố.
Ví dụ N=2i3j5k thì ước lớn nhất không chứa chính phương là 2.3.5
Chương trình:
Const max=10000;
function ngto(n: longint): boolean;
var i: longint;
begin
 nguyento:=false;
 for i:=2 to trunc(sqrt(n)) do
 if n mod i = 0 then exit;
 ngto:=true;
end;
var
 n,i,j,a: longint;
 f1,f2: Text;
 us:int64;
 nt: array[1..max] of longint;
begin
 Assign(f1,’CP.INP’); Reset(f1);
 Assign(f2,’CP.OUT’); Rewrite(f2);
 Readln(f1,n);
 for i:=2 to sqrt(N) do if ngto(i) then
 begin
 a:=0;
 j:=i;
 while (j<=n) do
 begin
 a:=a+n div j;
 j:=j*i;
 end;
 nt[i]:=a;
 us:=us*i;
 end;
 Write(f2,us);
Close(f1);
Close(f2);
end.
Bài toán 6: Nguyên tố tương đương
	Hai số tự nhiên được gọi là Nguyên tố tương đương nếu chúng có chung các ước số nguyên tố. Ví dụ các số 75 và 15 là nguyên tố tương đương vì cùng có các ước nguyên tố là 3 và 5. Cho trước hai số tự nhiên N, M. 
	Yêu cầu: Hãy viết chương trình kiểm tra xem các số này có là nguyên tố tương đương với nhau hay không.
Dữ liệu vào: trong file văn bản BAI3.INP:
	- gồm nhiều dòng, mỗi dòng ghi 2 số N và M cách nhau bởi dấu cách (0<=N,M<=106)
Dữ liệu ra: Ghi vào File BAI2.OUT
	- gồm nhiều dòng, mỗi dòng ghi số 1 nếu N và M là 2 số nguyên tố tương đương, ngược lại ghi số 0.
BAI6.INP
BAI6.OUT
75 15
8 27
1
0
Chương Trình
var f1,f2:text;
i,d,x,y:int64;
function ucln(a,b:int64):int64;
var tg:int64;
begin
 while b0 do
 begin tg:=a mod b; a:=b;b:=tg;end;
 ucln:=a;
end;
begin
 assign(f1,'bai6.inp');reset(f1);
 assign(F2,'bai6.out');rewrite(f2);
 readln(f1,x,y);
 d:=ucln(x,y);
 i:=2;
 while d>1 do
 if d mod i0 then inc(i)
 else
 begin while d mod i=0 do d:=d div i;
 while x mod i=0 do x:=x div i;
 while y mod i=0 do y:=y div i;
 end;
 if x*y=1 then write(f2,'co') else write(f2,'khong');
 close(f1);close(f2);
end.
Bài toán 7: Bài toán cổ
	Tương truyền rằng, ngày xưa có một mưu sĩ thấy dân chúng quá nghèo khổ nên ông ta đã đến thách đố đánh cờ cùng nhà vua nhằm lấy thóc trong kho đem phân phát cho dân nghèo. Nhà vua ra điều kiện nếu đánh thua nhà vua thì mưu sĩ sẽ bị chém đầu, ngược lại mưu sĩ sẽ được trọng thưởng bằng vật chất. Nếu đánh thắng cờ với nhà vua, mưu sĩ chỉ xin một điều đó là trong mỗi ô cờ gồm 8x8 ô thì lần lượt bỏ vào ô thứ 1: 1 hạt thóc, ô thứ 2: 1x2 hạt thóc, ô thứ 3: 1x2x3 hạt thóc, cho đến ô cuối cùng. Nhà vua nghe qua rất khoái chí và đồng ý ngay. Sau lần đấu cờ đó nhà vua đã mất rất nhiều kho lương thực cho dân nghèo. 
 	Do bản tính hiếu thắng của nhà vua, ông vẫn tiếp tục thách đấu với những tay cao thủ cờ khác trong thiên hạ nhưng bây giờ rút kinh nghiệm ông chỉ xuất trong kho ra bây giờ không phải là thóc nữa mà là vàng. Nguyên tắc để nhận được vàng sau khi đánh thắng nhà vua như sau:
Mỗi ô trong bàn cờ có một số. Con số này được gán vào như sau: 
- Ô số 1: 1
- Ô số 2: 	 1x2 = 2
- Ô số 3: 	 1x2x3 = 6
- Ô số 10 1x2x3x.x10 = 3 628 800 
- Ô số 21 1x2x3x.x21 = 51 090 942 171 709 440 000 
Số vàng nhận được chính là con số khác không đầu tiên kể từ hàng đơn vị lên phía trước của ô mà đối thủ sẽ chọn. Ví dụ, chọn ô số 10 thì sẽ được 8 lạng vàng, ô số 21 sẽ được 4 lạng vàng, 
Đối thủ chỉ được chọn mỗi lần một ô để nhận