Đếm số nguyên tố trong 1 dãy số. {Edited by HSG}

[thapchidao]

sacklove xem lại và giải thích thuật toán đi chứ!

[vipcuchuoi02]

1 số n là số nguyên tố nếu nó chỉ chia hết cho 1 và chính nó, tức là nếu nó ko chia hết cho bất kỳ số nào trong khoảng 2 -> n-1 thì là số nguyên tố.
Tuy nhiên chỉ cần kiểm tra trong khoảng 2 -> n div 2 (phần nguyên của phép chia n cho 2), bởi hiển nhiên n ko chia hết cho các số từ n div 2 + 1 -> n-1. Thuật toán của sacklove chắc cũng dựa trên điều này

VD với n = 17 thì cần kiểm tra xem 17 có chia hết cho các số từ 2 đên 17 div 2 = 8 hay ko (các số từ 9 đến 16 rõ ràng 17 ko chia hết)

[chautuanpro91]

1 số n là số nguyên tố nếu nó chỉ chia hết cho 1 và chính nó, tức là nếu nó ko chia hết cho bất kỳ số nào trong khoảng 2 -> n-1 thì là số nguyên tố.
Tuy nhiên chỉ cần kiểm tra trong khoảng 2 -> n div 2 (phần nguyên của phép chia n cho 2), bởi hiển nhiên n ko chia hết cho các số từ n div 2 + 1 -> n-1. Thuật toán của sacklove chắc cũng dựa trên điều này

VD với n = 17 thì cần kiểm tra xem 17 có chia hết cho các số từ 2 đên 17 div 2 = 8 hay ko (các số từ 9 đến 16 rõ ràng 17 ko chia hết)

Những kiến thức về số nguyên tố chắc ai cũng biết, nhưng thuật toán của sacklove dùng tới mảng boolean không biết để làm gì. Bạn sexy_killer nếu biết chắc thì mới nói nhé, tránh trường hợp các mem khác đọc bài chưa kĩ lại không hiểu, tưởng rằng thuật toán đó đúng như thế, nếu quả thật thuật toán đúng vậy thì không sao, nhưng nếu thuật toán khác như thế thì sẽ tai hại đó.

[seovg]

Thuật toán của sacklove theo mình hiểu thì là thuật toán sàng, hình như là sàng Eratosthenes nhưng cài theo cách chưa tối ưu, đúng không nhỉ [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]

[noithatdn]

Các bạn đừng đoán nữa! [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG] Mình hướng dẫn cách tìm nhá!
Lấy giấy nháp và bút ra. Rồi chạy chương trình bằng tay sẽ biết rõ nó hoạt động như thế nào thôi.
Những cách chúng ta hay dùng để xử lí như xử lí số thì cũng tốt nhưng đối với những cách dùng đến BOOLEAN (đúng/sai) thì đòi hỏi đầu óc phải tư duy trừu trượng hơn nhiều mới có thể xử lí và đưa 1 bài toán dài dòng, khó thành 1 bài dễ dàng.
Cách trên của Sacklove còn chiếm khá nhiều bộ nhớ vì dùng tới 4 vòng for. Nếu số lớn thì chạy xịt khói! Haha!

Cheers!

[mrtho88hnn]

Sr ! Mình đọc không kĩ đề. Mình nhầm là tìm các số nguyên tố trong 1 dãy số nguyên liên tiếp <= n .
Còn thuật toán đơn giản là nếu 2 số là số nguyên tố thì chắc chắn tích của chúng không phải là số nguyên tố. Cứ như vậy các tích sẽ dần bị loại, chỉ còn lại là các số nguyên tố .

[namnh]

Sử dụng chương trình con, bạn có thể viết như sau. Bạn sử dụng hàm như mình viết dưới đây có thuật toán tốn ít thời gian hơn là ở chương trình trên mình viết. Vì ở chương trình trên để kiểm tra số nguyên tố mình sẽ đếm xem nó có 2 ước. Còn ở chương trình dưới đây bạn chỉ cần kiểm tra xem x có chia hết 1 số bất kì từ 2 đến phần nguyên căn bậc 2của nó thì khẳng định nó không nguyên tố, ngược lại nó là số nguyên tố!

type mang=array[1..100] of integer;
Var A:mang;
i,N,dem:integer;
{Thu tuc nhap mang}
procedure Nhap (Var A:mang;n:integer);
Begin
For i:=1 to N do
 Begin
   write('A[',i,']=');
   Readln(A[i]);
 End;
End;
{Ham kiem tra 1 so co phai la so nguyen to hay khong}
Function sont(x:integer):boolean;
Var i:Integer;
Begin
sont:=x>1;
For i:=2 to trunc(sqrt(x)) do
 if x mod i=0 then
 Begin
   sont:=false;
   break;{Thoat khoi cong lap}
 End;
End;
{CHuong trinh chinh}
Begin
write('Nhap voa so phan tu cua day:');
Readln(N);
Nhap(A,N);
dem:=0;
For i:=1 to N do if sont(A[i])=true then dem:=dem+1;
write('trong mang co:',dem,' so nguyen to');
Readln
End.

profestional,,,hay lắm,cái mình đang cần