Thuật toán kiểm tra số nguyên tố trong Pascal

You are viewing this post: Thuật toán kiểm tra số nguyên tố trong Pascal

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 anvuongvilla.com.vn để có cách tìm số nguyên tố.

I. Video thuật toán kiểm tra số nguyên tố

II. Nội dung thuật 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ố :

Ý 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.

III. Thuật toán kiểm tra số nguyên tố trong Pascal

IV. 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.

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:

V. Một số bài toán tìm số nguyên tố trong mảng Pascal

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ố đó.

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ố.

Đố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!

The article is compiled and aggregated from many sources by An Vượng Villa.

See more articles in the same category here: Tin Học