Thuật toán kiểm tra số nguyên tố trong pascal và bài tập mở rộng

Like Tweet Pin it Share Share Email

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

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.

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.

Sau đây là chương trình 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).

program phan_tich_nguyen_to;
var m,k,j: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,'pt_nt.inp'); reset(f);
	read(f,m);close(f);
{----Mo file de ghi----}
	assign(f,'pt_nt.out'); rewrite(f);

  k:=m;
  while (k>2) and (ngto(k)=false) do
    	begin
      		j:=2;
		while (k mod j <>0) and (ngto(k)=false) and(j<k) do
			begin
				j:=j+1;
			end;
        	write(f,j,'.');
		k:=k div j;
	end;

  write(f,k);
close(f);
end.

Trên đây là 3 bài lập trình Pascal về số nguyên tố, qua bài này các bạn cần nắm vững

  • Thuật toán kiểm tra số nguyên tố (nên viết chương trình con)
  • Cách viết và gọi chương trình con
  • Cách nhập xuất dữ liệu từ file trong Pascal.

Xin chào và hẹn gặp lại các bạn!

Comments (0)

Trả lời

Your email address will not be published. Required fields are marked *