Thuật toán pascal về số nguyên tố!

[dongcambiz]

- Vấn đề đặt ra ở đây là thi tin học trẻ không chuyên dành cho HS cấp 2. Mà với trình độ toán học cấp 2, hS mới chỉ hiểu khái niệm số nguyên tố: " SNT là số chỉ có 2 ước là một và chính nó". Nếu ta sử dụng thuật toán SNT có trong SGK thì làm sao giải thích cho HS cấp 2 hiểu được. Xin các pro đề xuất thuật toán dễ làm nhưng HS cấp 2 hiểu được với trình độ toán học của cấp 2.
+++++++++++++++++++++++++++++++++++++++++++
Mình nghĩ ra thuật toán sau, làm good với chương trình nhưng nhào nặn thành một function thì không được. Các bạn góp ý cho với nhé
++++++++++++++++++++++++++
" Nhập vào một số nguyên từ bàn phím và kiểm tra xem số vừa nhập có phải là SNT hay không rồi xuất kết quả ra màn hình!"
*****************************************
program snt;
var so, d, i : integer;
begin
d:=0;
write (' Nhap so='); readln(so);
for i:=1 to so div 2 do
if so mod i =0 then inc(d);
if d=2 then writeln(' So vua nhap la SNT!')
elsse writeln('So vua nhap khong la SNT!');
readln;
end.
**************************

[lee_huynh306]

Vì cấp 2 nên mò mẫm chia từng số vậy mình nghĩ không thành vấn đề, mà cấp 2 học tới căn bậc 2 chưa? Nếu rồi thì xét tới sqrt(so) là được rồi.
Cái vòng lặp bạn nên cải tiến chút.



nguyen_to:=true;
For i:=2 to sqrt(so) do
if so mod i <> 0 then
begin
nguyen_to:=false;
break;
end;


À mà trong bài bạn hình như d=1 thì hiện lên SNT mới đúng thì phải :w00t:

[dongcambiz]

Thật ra thì lớp 9 đã học căn bậc 2. Tuy nhiên giảng giải thuật toán SNT có liên quan tới căn bậc 2 cảm thấy kiến thưc hơi rỗng, hs khó hiểu. Mình vận dụng kiến thức căn bản " số nguyên tố là số chỉ có 2 ước là 1 và chính nó" => mình sử dụng thuật toán tìm ước của số được nhập, nếu có 2 ước thì nó là snt và ngược lại thì không phải số nguyên tố. Cho nên d=2 thì mới là SNT.
+++++++++++++++++++++++
=> Theo riêng mình thì thuật toán dễ hiểu, vận dụng toàn kiến thức cơ bản. Tuy nhiên mình không thể viết nó thành function được. Xin các bạn góp ý thêm!

[lee_huynh306]

Bạn chỉ xét từ 1 đến so div 2, với trường hợp so là SNT thì ở đâu ra mà 2 lần chia hết, bạn đâu xét tới so đâu :|
Mà bạn là giáo viên à?:noexpress

[dongcambiz]

Bạn chỉ xét từ 1 đến so div 2, với trường hợp so là SNT thì ở đâu ra mà 2 lần chia hết, bạn đâu xét tới so đâu :|
Mà bạn là giáo viên à?:noexpress

- Mình viết ra hàm được rồi. Bạn xem thử chương trình này nhé. MÌnh tâm đắc ở chỗ với thuật toán này thì giảng lớp 8 cũng sẽ hiểu bạn à. Lớp 8 chưa học căn bậc 2.
++++++++++++++++++++++++++++++++++


program snt;
var a: integer;
{********************************}
function snt (so: integer): booloean;
var d, i: integer;
begin
d:=0;
snt:=false;
for i:=1 to so div 2 do
if so mod i = 0 then inc(d);
if d=1 then snt:=true;
end;
+++++++++++++++++++++++++++++++++++
begin
write (' Nhap so='); readln(a);
if snt(a) = true then writeln (' la so nguyen to!')
else writeln (' Khong la so nguyento!');
readln;
end.

============================================
= Mình đang làm công tác bồi dưỡng HSG tin học trẻ không chuyên. Đây là năm đầu tiên làm việc này nên còn nhiều hạn chế. Hy vọng bạn có thể chia sẻ kinh nghiệm cho mình với! thankss
+++++ MÌNH BẢO ĐẢM THUẬT TOÁN TRÊN LÀ DO MÌNH TỰ NGỘ RA ĐÓ, KHÔNG HỀ THAM KHẢO SÁCH NÀO CẢ.+++++++++

[langtusitinh225]

Mình thường làm như thế này


function kt(n:integer):boolean;
var i:integer;
begin
kt:=false;
for i:=2 to trunc(sqrt(n)) do
if n mod i=0 then exit;
kt:=false;
end;

Với n bất kỳ:


if kt(n) then write(n,' la so nguyen to')
else write(n,' khong la so nguyen to');

[lee_huynh306]

Mình xin lỗi nhưng phải nói thẳng, bạn nên xem lại kiến thức toán học của bản thân, bạn mắc phải những lỗi rất ư là... con nít. Để mình phân tích nhé:
- Khi so/2 < i < so thì 1 < so/i < 2 => chắc chắn so/i không bao giờ là số nguyên, vậy cớ gì phải cho vòng lặp chạy từ i đến so? => chạy đến so/2 (nếu không chịu sqrt(so))là được rồi.
- Giả dụ so = 4, function bạn chạy nó sẽ xét i toàn bộ từ 1 - 4, đây là sự phí phạm thời gian hết sức trẻ con, mà khi đi thi thì hơn nhau một vài ms đã thắng rồi. Trong khi chỉ cần xét tới i = 2 là biết chắc chắn 4 không phải là số nguyên tố, tổng quát lên tới số 1 tỷ thì bạn phải chạy vòng lặp 1 tỷ lần mới có kết quả trong khi người ta lặp có 1-2 lần là người ta biết kết quả rồi.
- Như bài trên đã nói, mặc định số nào cũng chia hết cho 1, không phải xét, phí thời gian. Mặc định tự hiểu. Thi học sinh giỏi là cuộc thi dành cho những người giỏi, biết tìm cách optimize thuật toán thật nhanh, thật gọn chứ không phải bám sát lý thuyết mà làm cho dài dòng.
Nói thành ra mít lòng chứ bạn đi thi chưa chắc làm lại tụi nhóc kia nữa chứ ở đó mà... T.T

[dongcambiz]

he, đâu có sao! Nói thẳng coi như góp ý. thankss bạn. Mình cũng biết vấn đề optimize thuật toán. Ý tưởng của mình là truyền đạt cơ bản đã. Mình chỉ có 4 tháng để bồi dưỡng hs mà trước giờ chưa từng biết gì ngoài word. Kiến thức căn bậc 2 mới học bên toán. Nếu bồi dưỡng cấp 3 thì dễ dàng hơn rồi.
=> Mình nghiệm ra điều bạn nói và kiểm tra trên máy rồi. cảm ơn!

[=========> Bổ sung bài viết <=========]


Mình thường làm như thế này


function kt(n:integer):boolean;
var i:integer;
begin
kt:=false;
for i:=2 to trunc(sqrt(n)) do
if n mod i=0 then exit;
kt:=false;
end;

Với n bất kỳ:


if kt(n) then write(n,' la so nguyen to')
else write(n,' khong la so nguyen to');


=>> MÌnh có dùng thuật toán này mà, vấn đề là làm sao vận dụng với học sinh lớp 8?

[huan1802]

mình có một thuật toàn có thể nhanh hơn chút:

function ktnguyento(x:longint):longint;
var i:longint;
begin
i:=2;
while (x mod i <>0) and (x>=2) then
i:=i+1;
if i=x then
ktnguyento:=1;{nếu là số nguyên tố}
else
ktnguyento:=0;{nếu ko là số nguyên tố}
end;

procedure ketqua;
var i:longint;
begin
write('Nhap so x: ');
readln(x);
if ktnguyento(x)=1 then
writeln('So ',x,' là số nguyên tố')
else
writeln('So ',x,' ko la so nguyen to');
end;

bài này có thể tốn ít thời gian hơn

[hcvtpt]

mình nghĩ thuật toán số nguyên tố là thuật toán rất căn bản và dễ hiẻu do chỉ cần đùng 1 vòng lặp là giải quyết được.
nếu cần sd thì mình thường dùng 2 cách là dùng for để đếm ước hoặc dùng một biến tạm là kt (boolean) để kiểm tra trạng thái.
mình viết vòng lặp như thế này: for i:=2 to n-1 do
// chẳng cần giải thích là n div 2 hay j cả,.. vì nó cũng chẳng quan trọng lắm.
và chẳng cần chạy nhanh nữa.
:D

[aukey2006vn]

với học sinh lớp 8 mà làm như mấy bạn sau thì học sinh càng rối thêm, còn bài đầu tiên của bạn chưa chính xác một số chỗ cần sửa lại. để hoàn chỉnh có thể làm như sau:
<Code>
program snt;
var so, d, i : integer;
begin
d:=0;
write(' Nhap so='); readln(so);
if (so=2) or (so=3) then writeln('So vua nhap la SNT!')
else if (so>3) then
begin
for i:=2 to so div 2 do
if so mod i=0 then inc(d);
if d=0 then writeln('So vua nhap la SNT!')
else writeln('So vua nhap khong la SNT!');
end
else writeln('So vua nhap khong la SNT!');
readln;
end.
</code>

[hoangphong1996]

xin chào các anh các chị
em năm nay học lớp 10 và đang học pascal để thi....
thuật toán: em nghĩ bài này nên cho i chạy từ 1 tới n, nếu n mod i = 0 thì gán so:= so + 1
nếu so=2 thì số đó là số nguyên tố
code:
var N, so, i: integer;
begin
so:= 0;
write('nhap so N: '); readln(N);
for i:= 1 to n do if (n mod i = 0) then so:= so + 1;
if so = 2 then writeln(n,' la so nguyen to')
else writeln(n,' khong phai la so nguyen to');
readln
end.

[auauau97]

xin chào các anh các chị
em năm nay học lớp 10 và đang học pascal để thi....
thuật toán: em nghĩ bài này nên cho i chạy từ 1 tới n, nếu n mod i = 0 thì gán so:= so + 1
nếu so=2 thì số đó là số nguyên tố
code:
var N, so, i: integer;
begin
so:= 0;
write('nhap so N: '); readln(N);
for i:= 1 to n do if (n mod i = 0) then so:= so + 1;
if so = 2 then writeln(n,' la so nguyen to')
else writeln(n,' khong phai la so nguyen to');
readln
end.
cho i chạy từ 1 tới n thì mệt quá, bạn có thể cho chạy từ 2 tới căn n là ổn rồi:
for i:=2 to round(sqrt(n)) do là được

[haplinhavxt]

Vậy nếu n<= 10^18 thì bạn sẽ chạy như thế nào?

[ThangA3]

Vậy nếu n<= 10^18 thì bạn sẽ chạy như thế nào?
TH này có lẽ phải xài cái này.
1 số là sô nguyên tố THÌ số đó mod 6 = 1 or = 5, điều ngược lại thỳ ko xảy ra.
kiểu dữ liệu thì chắc chắn là extended rùi.

[HGMinh95]

TH này có lẽ phải xài cái này.
1 số là sô nguyên tố THÌ số đó mod 6 = 1 or = 5, điều ngược lại thỳ ko xảy ra.
kiểu dữ liệu thì chắc chắn là extended rùi.
2 mod 6 = 2 mà????????

[ThangA3]

2 mod 6 = 2 mà????????
sorry, mình bị thiếu:
a nguyên tố, a>3 => a mod 6 = 1 or 5.
VD:
5 mod 6 =5;
7 mod 6 =1;
11 mod 6 = 5;
19 mod 6 = 1;
29 mod 6 = 5 v.v.v..... và nhìu nữa ( trừ 2 và 3 thôi )

[haplinhavxt]

25 thì sao bạn! 1 số nguyên tố => có dạng 6*k+ 1 hoặc 6* k- 1! Đây là => chứ ko phải là <=>! Ví

[ThangA3]

25 thì sao bạn! 1 số nguyên tố => có dạng 6*k+ 1 hoặc 6* k- 1! Đây là => chứ ko phải là <=>! Ví
Ừ thì sao ???????? có gì sai đâu :)

[haplinhavxt]

Vậy cho bạn số có 9999...7 (16 số 9) bạn định kiểm tra số này ntn?? (Kiểu dữ liệu chỉ là qword, real cũng được nhưng sài số thực làm gì cho mệt người =))))

[Em Chán Gà]

= Mình đang làm công tác bồi dưỡng HSG tin học trẻ không chuyên. Đây là năm đầu tiên làm việc này nên còn nhiều hạn chế. Hy vọng bạn có thể chia sẻ kinh nghiệm cho mình với! thankss
+++++ MÌNH BẢO ĐẢM THUẬT TOÁN TRÊN LÀ DO MÌNH TỰ NGỘ RA ĐÓ, KHÔNG HỀ THAM KHẢO SÁCH NÀO CẢ.+++++++++[/QUOTE]

Hi bạn!
Thuật toán trên có thể nói là kinh điển, bởi vì nó sát với lý thuyết.
Nhưng Học lập trình nói chung và Pascal nói riêng, thì thuật toán và tư duy mới là cái quan trọng.
Theo ý tôi thì phân tích như sau (theo tôi nghĩ học sinh cấp II sẽ rất dễ hiểu)
Thuật toán:
Lần lượt xét:
- X là 1,2,3,5,7,11 ==> là số NT
Nếu không phải các số trên thì:
- Chia số đó lần lượt cho 2,3,4..... số/2. Nếu gặp một số mà số đó chia hết thì dừng lại và kết luận nó không phải số nguyên tố, ngược lại nó là số nguyên tố.
Sơ đồ thuật toán:
http://sanchoinho.com/images/SNT.png (http://sanchoinho.com/images/SNT.png)

[Em Chán Gà]

Chương trình:


Program SoNguyenTo;
Var
x,n:Integer;
SNT: Boolean;
Begin
SNT:=False;
x:=2;
Write('Nhap So N:'); Readln(n)
If (n=1) or (n=2) or (n=3) or (n=5) or (n=7) or (n=11) {*}
Then SNT=True
Else
Repeat
If (n mod x)>0 then SNT= False
Else x:=x+1;
Until (x<(N Div 2)) or (SNT=False);
If SNT then Writeln(N, 'Là Số Nguyên Tố')
Else Writeln(N, ' Không Là Số Nguyên Tố');
Readln;
End.



{*} Thực ra không cần đoạn này, nhưng để tính hiệu suất chương trình thì nên có.

[wuanwu]

Nếu không sử dụng sqrt(n) thì hãy so sánh k*k với n. Mình không có Pascal nên code trực tiếp vào đây vậy. Chú ý rằng 1 không là số nguyên tố. Giải thuật là, kiểm tra từ k = 2 trở đi, nếu n không chia hết cho k thì tăng k lên 1, nhưng chỉ khi k*k < n, tức k < sqrt(n).


function IsPrime(n: word): boolean;
var k: word;
begin
if n <= 1 then IsPrime := False
else
begin
k := 2;
while (k*k < n) and (n mod k <> 0) do k := k + 1;
if k*k > n then IsPrime := True
else IsPrime := False
end
end;

[vanban1]

mình có một thuật toàn có thể nhanh hơn chút:

function ktnguyento(x:longint):longint;
var i:longint;
begin
i:=2;
while (x mod i <>0) and (x>=2) then
i:=i+1;
if i=x then
ktnguyento:=1;{nếu là số nguyên tố}
else
ktnguyento:=0;{nếu ko là số nguyên tố}
end;

procedure ketqua;
var i:longint;
begin
write('Nhap so x: ');
readln(x);
if ktnguyento(x)=1 then
writeln('So ',x,' là số nguyên tố')
else
writeln('So ',x,' ko la so nguyen to');
end;

bài này có thể tốn ít thời gian hơn

thank anh nha đúng bài cần tìm

[vanban1]

Chương trình:
{*} Thực ra không cần đoạn này, nhưng để tính hiệu suất chương trình thì nên có.
hơ , cái này thuật toán bên dưới nó tự tính thêm vào cho dài hả anh

[Em Chán Gà]

hơ , cái này thuật toán bên dưới nó tự tính thêm vào cho dài hả anh:yes: Dài là trong bài thì dài, nhưng khi chạy nếu nhập số nhỏ thì khỏi lặp vòng nào.


Chú ý rằng 1 không là số nguyên tố.


Chết cha, nhầm kiến thức rùi. Đúng 1 là số đặc biệt, không phải SNT, cũng không phải hợp số.

[tungdepzai]

tôi nghĩ là 'for i:=1 to so do' chứ(của bạn là for i:=1 to so div 2 do')
Bởi vì như ban thì số 4 cũng là số nguyên tố. Vì d=2 và 3 không fai là sô nguyên tố vì d<>2(d=1).

[Em Chán Gà]

Write('Nhap So N:'); Readln(n) If (n=1) or (n=2) or (n=3) or (n=5) or (n=7) or (n=11) {*} Then SNT=True



Nhờ khúc này nè bạn, chỉ chạy lặp khi lớn hơn 11. Còn tại sao lại chỉ tới Nó div 2 thì chắc ai cũng hiểu.

[ThangA3]

Vậy cho bạn số có 9999...7 (16 số 9) bạn định kiểm tra số này ntn?? (Kiểu dữ liệu chỉ là qword, real cũng được nhưng sài số thực làm gì cho mệt người =))))
extended là kiểu số nguyên mà bạn.
nếu cho 99999...7 thỳ xét nó có mod 6 =1 or 5 ko, nếu đc thỳ xét như
bình thường

[nhok_LTK]

extended là kiểu số nguyên mà bạn.
nếu cho 99999...7 thỳ xét nó có mod 6 =1 or 5 ko, nếu đc thỳ xét như
bình thường

extended là kiểu số thực màk =="

[ThangA3]

extended là kiểu số thực màk =="
ừ , mình nhầm,..............................

[thecuong064]

Mấy bác ờ trang 1 hay thật. Lớp 7 đã học căn bậc hai rồi

[thecuong064]

Mà sao dạo này forum vắng vậy, chả thấy ai

[mrjokes]

theo minh` de hs cap 2 hieu 1 cach de nhat la`
For i:=1 to so do
If so mod i=0 then d:=d+1;
If d=2 then write('nguyen to') else write('ko nguyen to');
Cach nay` giong' nhu dinh nghia trong sgk nen de hieu hon

[kickbuttowski]

nho cac ban lam jup minh bai nay dc ko?
Tim tat ca cac so nguyen to tu 1 den 100.
tim tong tat ca cac so nguyen to tu 1 den 100

[kickbuttowski]

y' we^n!
chi dung for to do, while do, va menh de if
!!!!!!!!!!!!!!!!!!

[cunbong24]

Các PAC "lói " nhiều lời về thuật toán cơ bản này quá!. Mọi sách Tây, Tàu, ta đều định nghĩa số nguyên tố chặt chẽ và đầy đủ như sau: Số nguên tố là số chỉ chia hết cho chính nó và 1; số 1 không phải là số nguyên tố. (Vì vậy hiển nhiên số 2 là số nguyên tố bé nhất trong "làng" các số nguyên tố!). Mình đề xuất một code cho bài toán này chả liên quan gì tới căn bậc hai cả. (chỉ dùng khái niệm chia hết hoặc là ước số như các PAC đã nêu!!). Code này về bản chất cũng chẳng khác của các PAC đâu. Nhưng đây là 1 Program hoàn chỉnh và chắc chắn hs THCS hiểu được

Program Ktra_tinh_nto;
Uses crt;
Var n:Integer;
FUNCTION Ktra_nto(k:integer):Boolean;
Var i:integer;
Begin
If k=1 then Ktra_nto:=False
Else If k=2 then Ktra_nto:=true
Else Begin
Ktra_nto:=true;
For i:=2 to k-1 do
If (k MOD i=0) then Ktra_nto:=False;
End;
End;
{Ch_trinh chinh:}
Begin clrscr;
Writeln(#32:25,'GO SO KHONG DE THOAT.'); WRITELN;
Write('Nhap mot so nguyen duong n='); Readln(n);
While n>0 do
Begin
If Ktra_nto(n) then Writeln(n,' la so nguyen to.')
Else Writeln(n,' khong phai la so nguyen to !');
Write('Nhap mot so nguyen duong n=');
Readln(n);
End;
End.

[huy20144]

function Nguyen_To(n:longint):boolean;
begin
if n<2 then
exit(false)
else
for i:=2 to trunc(sqrt(n)) do
if n mod i =0 then
exit(true);
exit(true);
end;

[mini_bestboy]

Các bạn làm thường là chia vét cạn từ 2 đến N, hoặc căn N (dùng hàm thư viện) như vậy nếu N cao sẽ rất tốn kém thời gian.

Cách nhanh tốt và đơn giản nhất là dùng sàng Eratosthenes, theo định lí thì các số nguyên tố sẽ không chia hết cho các số nguyên tố đứng trước nó, mà số lượng số nguyên tố thì rất ít nên thuật toán chạy sẽ nhanh hơn. Về kĩ thuật, cứ dò được 1 số nguyên tố nào đó thì cho vô 1 mảng, lúc xét số nguyên tố chỉ cần chia cho các số trong mảng là được.