TÌm SỐ NguyÊn TỐ???

[gac_kiem____]

ko tối ưu.
VD với số 169:
chương trình đó phải chia cho 1,2,3,4,5,6,7,8,9,10,11,12,13.
tui chỉ cần chia cho các số 2,3,5,7,11,13 thế thôi.
lưu các số nguyên tố nhỏ hơn n lại rồi chia n cho các số nguyên tố nhỏ hơn n.

->>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>>>>>>>>
bộ ông thích tối ưu lắm hả.
bài giải chỉ là để tham khảo.
còn tối ưu cách ông như vậy có tối ưu chưa.

[tranmauhanh]

Mấy anh giúp em giải bài này:
Nhập vào 1 dãy, xác định xem trong dãy có bao nhiu số nguyên tố ? em ko biết là làm sao để phân biết được số nguyên tố với những số khác.

Số nguyên tố là số chia được cho nó và sô 1. Để xác định n có phải số nguyên tố ko, nếu n không chia hết cho các số từ 2 đến n/2( trừ số 2 à nha). Như vậy cần viết một cái hàm xác định số nguyên tố. Trong một dãy, có bộ đếm nếu là số nguyên tố thì bộ đếm tăng lên 1, như vậy sẽ xác định có bao nhiêu số nguyên tố trong dãy.Mình không thể viết cụ thể ra đây, vì không có thời gian và lâu quá cũng quên hết mấy cái ngôn ngữ lập trình rồi.

[Phóng viên BBC]

Đối với Pascal mà xài lệnh BREAK hay là GOTO hay là EXIT gì đó thì coi như không, vậy thì học Pascal để làm gì.
Xem anh nè:

uses crt;
var A:array[1..100] of integer;
i,j,N,dem:byte;
ngto:boolean;
begin
clrscr;
{--------------------------------------------------------------------------------------}
write('N = ');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
if A[i] <=1 then ngto:= false else
if A[i] <4 then ngto:= true else
begin
ngto:=true;
For j:= 2 to trunc(sqrt(a[i])) do
if (A[i] mod J)= 0 then ngto:=false;

end;
if ngto=true then dem:=dem+1;
end;
{--------------------------------------------------------------------------------------}
writeln('So chu so nguyen to la: ',dem);
readln;
end.

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

Thuật toán tìm nguyên tố:
1.Nhập số nguyên N
2.Nếu n<=1 thì không là nguyên tố rồi kết thúc.
3.Nếu n<4 thì là nguyên tố rồi kết thúc.
4.Nếu n>=4 thì ta xét trong phạm vi của đoạn [2,phần nguyên căn bậc hai của N], nếu N có nghiệm trong phạm vi đó thì không là nguyên tố rồi kết thúc.
5.N là nguyên tố rồi kết thúc.

[nhat_truong]

Tui có bài này mời các bạn giải giúp
MỘt chiếc xe gây tai nạn sau đó bỏ trốn. Biết rằng biển số xe là một số nguyên tố có 3 chữ số và là một số đối xứng và khi chuyển số đó sang hệ nhị phân ta cũng được một số đối xứng. Là một nhà tin học em hãy giúp các nhà điều tra tìm ra chiếc xe gây tai nạn.

Program Bien_so_xe;
Var n:Integer;

Function ktnt(n:Integer):Boolean;
Var i:Integer;
Begin
.. ktnt:=False;
.. For i:=2 to trunc(sqrt(n)) do
..... If n mod i=0 then exit;
.. ktnt:=true;
End;

Function Palindrom(s:String):Boolean;
Var i:Integer;
Begin
.. Palindrom:=False;
.. For i:=1 to length(s) div 2 do
..... If s[i]<>s[length(s)-i+1] then exit;
.. Palindrom:=True;
End;

Function Nhi_Phan(n:Integer): String;
Var s,c:String;
Begin
.. s:='';
.. While n<>0 do
..... Begin
........ Str(n mod 2,c);
........ s:=s+c;
........ n:=n div 2;
..... End;
.. Nhi_Phan:=s;
End;

Function KT(n:Integer):Boolean;
Var s:String;
Begin
.. KT:=true;
.. If not(ktnt(n)) then KT:=false;
.. Str(n,s);
.. If not(Palindrom(s)) then KT:=false;
.. If not(Palindrom(Nhi_Phan(n))) then KT:=false;
End;

BEGIN
.. For n:=100 to 999 do
..... If KT(n) then Writeln('Bien so xe can tim: ',n);
.. Readln;
END.

Em chưa test thử, sai đừng chửi nhé

[Heroboss12]

Mấy anh giúp em giải bài này:
Nhập vào 1 dãy, xác định xem trong dãy có bao nhiu số nguyên tố ? em ko biết là làm sao để phân biết được số nguyên tố với những số khác.

Theo em code the nay
function ktnto(x:integer):boolean;
var i:integer;
begin
if x>2 then
for i:=2 to trunc(sqrt(x)) do
if x mod i=0 then ktnto:=false;
end;
procedure xuly;
var d,n,i,so:integer;
begin
read(n);
for i:=1 to n do
begin
read(so);
if ktnto(so) then inc(d);
end;
write(d);
end;
begin
xuly;
end.

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

the thoi ai co y kiem cu chi giao

[troidat1234]

Hehe, tui xin mạng phép lật lại bài cũ
Đa số các bạn đều giải đúng hết hehe chúc mùng, chúc mừng.
Nhưng các bạn mắc chung một lỗi là để kiểm tra một số nguyên tố, các bạn cho chạy i:=2 to n (hay Sqrt(n) cũng như nhau) rùi kiểm tra n có chia hết cho i không, cách này đúng nhưng không hay.
Thí dụ:
trong dãy có hai số 17 và 23 thì các bạn phải chay 2 vòng lặp
Tại sao các bạn không dùng một mãng lưu trữ lại các số nguyên tố nhỏ hơn n (hay Sqrt(n) cái này hay hơn) rùi kiểm tra số m tiếp theo n bằng cách
giải thuật
kiểm tra tính chia hết của m cho các số nguyên tố nhỏ hơn m (sqrt(m))
else (m>n)
thì kiểm tra tiếp thêm các số nguyên tố từ sqrt(n) đến sqrt(m).

Như vậy các bạn có thể kiểm tra được dãy n số rất lớn mà không tốn nhiều thời gian. vì số số nguyên tố từ 2 đến sqrt(n) là không nhiều.

Bên cạnh đó các bạn cũng có thể kiểm tra dãy n rất nhiều số và các số trong dãy là số lớn.(cái này bang hang_vt chắc chắn sẽ làm được . tui hi vọng code của bạn hang_vt với giải thuật tìm dãy nhiều số và số lớn

[hang_vt]

cách của a nói là sàng nguyên tố ùi . N~ bài đơn giản ntn đâu có cần dùng đến thuật toán đó
mà đâu phải chỉ e code đc . Trong 4rum nhiều ng pro hơn e lắm

[bld]

tìm số nguyên tố thứ n

dem:=0; a[2]:=false;
for i:=2 to n do 
 begin
  if a[i]=true then inc(dem);
  if dem=n then break;
  a[i*2]:=false;
 end;
writeln(a[i]);

[hang_vt]

ý tưởng là ntn vậy bld . Mảng a lúc đầu ntn mà lại xét dk a[i]=true . Post đầy đủ ct c tham khảo vs

[bld]

nhận xét : với 1 số a thì 2a không phải là số nguyên tố . lúc đầu đánh dấu a[2]=true vì 2 là số nguyên tố . cho i chạy từ 2 trở lên với mỗi i như vậy lại đánh dấu 2i là false ( hợp số ) . số nào mà có i=true thì chắc chắn là số nguyên tố rồi
code trên em có nhầm tí chút

a[2]:=true;dem:=1;

mới đúng