Bài 1: Viết chương trình nhập vào số nguyên n. Tính tổng các số nguyên tố nhỏ hơn n
Vd: Nhập vào số nguyên 4( các số nguyên tố nhỏ hơn 4 là 2,3 )è xuất ra S=5
Bài 1: Viết chương trình nhập vào số nguyên n. Tính tổng các số nguyên tố nhỏ hơn n
Vd: Nhập vào số nguyên 4( các số nguyên tố nhỏ hơn 4 là 2,3 )è xuất ra S=5
uses crt;
var i,s,n:longint;
function snt(x:longint):boolean;
var j:longint;
begin
snt:=true;
if x<1 then snt:=false else
for j:=2 to trunc(sqrt(x)) do
if x mod j=0 then snt:=true;
end;
BEGIN
write('nhap n: '); readln(n);
s:=0;
for i:=2 to n-1 do if snt=true then s:=s+1;
write('tong cac snt <',n,' la:' s);
readln
end.
Code viết cẩu thả sai cú pháp tùm lum. Mà dẫu có viết đúng cú pháp thì giải như thế này cũng chỉ được tối đa 5/10.
1. Giải thuật xét số nguyên tố quá ấu trĩ. Gải thuật tối thiểu phải là:
Xét bit nhỏ nhất, nếu 0 thì là số chẵn. Nếu 1 thì là số lẻ, tính tiếp.
Vòng lặp khởi từ sô 3, và bước nhảy 2 (không cần thử chia số chẵn).
2. Nhưng bài này là cần tìm các số nguyên tố nhỏ hơn n. Cho nên dùng hàm xét số nguyên tố đơn độc là sai. Giải thuật đúng là lập một mảng giữ các số nguyên tố tìm được.
2.1 muốn thử 1 số nguyên tố thì ta chia thử nó cho các số nguyên tố nhỏ hơn hay bằng căn của nó.
2.2 khi tìm các số nguyên tố nhỏ hơn n thì ta chỉ tính số lẻ và lướt qua số chẵn.
Mấy bác để tui.
- - - Updated - - -
bài này quá dễ.
program ng_to;
ues crt;
var i,n,j,k,l:integer;
function ngto(n:integer):boolean;
var kt:boolean;
i,s:integer;
begin
s:=0;
kt:=false;
for i:=1 to n do
if n mod i=0 then s:=s+1;
if s=2 then kt:=true;
ngto:=kt;
end;
begin
clrscr;
write('Nhap so n:');readln(n);]
t:=0;
for i:=1 to n-1 do
if ngto(i) then t:=t+i;
writeln('Tong cac so ngto nho hon ',n,' la: ',t);
readln
end.
mình nghĩ cái function ngto nên thế này thì hơn:
function ngto(n:integer):boolean;
var i:integer;
begin
if n<2 then ngto:=false else
if n<4 then ngto:=true else
begin
ngto:=true;
for i:=2 to trunc(sqrt(n)) do
if n mod i=0 then ngto:=false;
end;
end;
Sao vậy mình thấy đúng mà ?
function của mình chỉ for i tới phần nguyên của căn n nên nó sẽ làm giảm thời gian chạy chương trình, vì ở đây ta chỉ cần tìm thấy 1 i mà n chia hết cho i thì n đó ko phải là số nguyên tố rồi
-Còn cái của mình thì kiểm tra xem số đó có 2 ước hay không.
----> Nếu có 2 ước thì số đó là số nguyên tố ngược lại thì không phải (bởi vì số nguyên tố chỉ có 2 ước là 1 và chính nó).
Mình thì chưa biết function của bạn đúng hay sai (vì chưa thử),nhưng theo cách nói thì có vẻ time chạy chương trình của bạn nhanh hơn.
Trong khi đó thì function của mình thì phải chạy hết vòng for để kiểm tra nên time chạy chương trình có thể sẽ chậm hơn so với cái của bạn.
Dùng sàng nguyên tố để giảm độ phức tạp,tg chạy nhah hơn
Bookmarks