Lập trình Pascal – Số nguyên tố trong dãy – HSG tin Bảo Lộc 1819 – Ôn Thi HSG

Xin giới thiệu với các bạn bài số 2 trong đề thi HSG tin 9 TP Bảo Lộc năm học 2018 – 2019 đó là bài  Số nguyên tố trong dãy. Dưới đây là các bài tập kiểm tra số nguyên tố pascal mới nhất hãy tham khảo với onthihsg ngay nhé các bạn.

Video hướng dẫn số nguyên pascal

1. Kiểm tra số N có phải là số nguyên tố trong pascal

Ví dụ:             N = 19            Kết quả là: 19 la so nguyen to

N = 33            Kết quả là: 33 khong phai la so nguyen to

Yêu cầu: Input:   N, là số tự nhiên bất kỳ.

Output: Trả lời “N la so nguyen to”

hoặc “N khong phai la so nguyen to” tùy theo N.

Lưu ý: Số nguyên tố là số chỉ có thể chia hết cho 1 và chính nó ( N ).

Ngược lại, N là không phải là số nguyên ==> N chia hết cho một số trong khoảng từ 2 đến (N-1).

Hướng dẫn cách tìm số nguyên tố trong pascal

Bài toán được thực hiện qua 3 bước cụ thể như sau:

–  Thông báo nhập liệu, và nhập dữ liệu vào cho N

–  Tiến hành kiểm tra N có phải là số nguyên tố hay không:

–  Xuất câu trả lời “N la so nguyen to” hoặc “N khong phai la so nguyen to” tùy theo giá trị của biến

Chương trình:

 

2. Khái niệm số nguyên tố

Số nguyên tố là số nguyên dương có duy nhất 2 ước phân biệt là 1 và chính nó. Lưu ý: Số 1 không phải số nguyên tố do chỉ có 1 ước.

3. Ý tưởng kiểm tra số nguyên tố

1. Nếu số đó bé hơn 2, kết luận không phải số nguyên tố.

2. Đếm số ước của x trong đoạn từ 2 đến căn bậc hai của x. Nếu số đó không có ước nào trong đoạn từ 2 đến căn bậc hai của x thì nó là số nguyên tố. Ngược lại thì không phải. Như vậy, nếu bạn đếm từ 1 thay vì 2 thì x là số nguyên tố khi ta đếm được 1 ước số trong đoạn từ 1 đến căn bậc hai của x.

4. Một số bài toán viết chương trình về số nguyên tố

Bài 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.inpDữ liệu ra file: Sum_nt.outChứ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 và viết chương trình tìm số nguyên tố pascal

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

 

 

Bài 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.inpDữ liệu ra file: pt_nt.outChứ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).

 

 

Bài 3. Cách in ra các số nguyên tố nhỏ hơn hoặc bằng N (N là số nguyên không âm được nhập từ bàn phím).

Program CAC_SO_NGUYEN_TO;

Uses crt;

Var n,i,t: integer;

Begin

Clrscr;

Writeln(‘IN RA CAC SO NGUYEN SO <=N’);

Writeln(‘————————–‘);

Write(‘Nhap n = ‘);readln(n);

If n<2 then

Writeln(‘Khong co so nguyen to nao <=’,n)

Else

Begin

Writeln(‘Cac so nguyen to <= ‘,n,’ la:’);

For i := 2 to n do

Begin

t:= 1;

Repeat

t:= t+1;

Until ( i mod t = 0) or ( t*t>i ) ;

If( t*t>i) then

Write(i:4);

End;

Readln;

End.