# GÓC SÁNG TẠO > Khu vực lập trình > Pascal/Delphi/Kylix >  Đếm số nguyên tố trong 1 dãy số. {Edited by HSG}

## tenten

Mình đang muốn tìm một đoạn code thực hiện đếm xem trong một dãy số nguyên có bao nhiêu số nguyên tố. Cứ giả sử là n<=100 nhé!

----------


## nguyentientu4497

Mình đang bận phải nấu cơm, bài này rất đơn giản ở trên topic rất nhiều rồi. Bạn tìm xem nếu không để tối mình gõ cho nhé!

----------


## zincos

```
uses    crt;
var     a:array[1..101] of boolean;
        i,j,n,d:byte;
begin
        write('nhap n:');readln(n);
        d:=0;
        a[1]:=false;
        for i:=2 to n do a[i]:=true;
        for i:=2 to n div 2 do
        for j:=2 to n div i do a[i*j]:=false;
        for i:=1 to n do
        if a[i] then inc(d);
        write(d);
        readln;
end.
```

----------


## quechi

Đây là trong trường hợp riêng biệt phải không? Mình có một bài này, không phải khó nhưng mà mình k biết ghép lại. Bạn có thể viết chương trình giùm mình để mình tham khảo được không? Đề bài như sau. Nhập vào một dãy số nguyên n (n<=100) Thực hiện đếm xem trong dãy số này có bao nhiêu số chẵn, bao nhiêu số lẻ, bao nhiêu số nguyên tố.

----------


## inbaongoc007

```
var A:array[1..100] of integer;
i,j,N,d,dem:integer;
Begin
write('Nhap vao so phan tu cua day:');
Readln(N);
For i:=1 to N do
  Begin
    write('A[',i,']=');
    Readln(A[i]);
  End;
  dem:=0;
For i:=1 to N do
 Begin
 d:=0;
 For j:=1 to A[i] do
  if A[i] mod j =0 then d:=d+1;
  if d=2 then dem:=dem+1;
End;
write('trong mang co:',dem,' so nguyen to');
Readln
End.
```

----------


## giangitnguyen

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.

```

----------


## ringhn9x

> 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ố!
> 
> 
> ```
> var A:array[1..100] of integer;
> i,N,dem:integer;
> {Thu tuc nhap mang}
> procedure Nhap (Var A:mang;n:integer);
> Begin
> ...


lehang viết cái thủ tục nhập để làm gì vậy ? Bạn đâu có dùng tới nó .
Mà hình như cấu trúc của thủ tục ấy ko đúng thì phải :-?

----------


## thanhluantm

Mình copy nhầm và mình vừa sửa lại ở trên rồi đó! Cám ơn sacklove

----------


## binhseo2800

Thuật toán của sacklove như nào thế nhỉ?

----------


## blogwhey1

Mình cũng chẳng hiểu thuật toán của sacklove, bạn có thể giải thích được không. Mà bạn đã viết đủ chương trình đâu, đã nhập vào các phần tử mảng đâu, mà a_ là boolean thôi!_

----------


## 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);
> ...


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

----------

