K
khanhvytl2001
[TẶNG BẠN] TRỌN BỘ Bí kíp học tốt 08 môn
Chắc suất Đại học top - Giữ chỗ ngay!!
ĐĂNG BÀI NGAY để cùng trao đổi với các thành viên siêu nhiệt tình & dễ thương trên diễn đàn.
Cho chương trình pascal sau:
uses windows;
const fi='prime.inp';
fo='prime.out';
var x:int64;
f,g:text;
time:longint;
function isprime(n:int64):boolean;
var i:int64;
begin
isprime:=true;
if n<2 then
begin
isprime:=false;
exit;
end;
i:=2;
while i<=trunc(sqrt(n)) do
begin
if n mod i=0 then
begin
isprime:=false;
exit;
end;
inc(i);
end;
end;
begin
time:=gettickcount;
assign(f,fi);reset(f);
assign(g,fo);rewrite(g);
readln(f,x);
if isprime(x) then
writeln(g,1)
else
writeln(g,0);
time:=gettickcount-time;
writeln(g,time);
close(f);
close(g);
end.
Chương trình trên dùng để kiểm tra số nguyên tố: đọc từ file prime.inp số nguyên x, kiểm tra xem x có phải là số nguyên tố hay không. Nếu x là số nguyên tố thì ghi vào file prime.out số 1, ngược lại thì ghi số 0. Dòng thứ hai của file prime.out ghi thời gian chạy chương trình (tính bằng mili giây).
Nếu chạy chương trình trên để kiểm tra số nguyên tố 999999999999999989 thì sẽ hết hơn 24000 mili giây (khoảng 24 giây). Các em có thể copy chương trình và chạy thử trên máy tính của mình.
Yêu cầu: em hãy cải tiến (viết lại) hàm isprime của chương trình trên để có thể chạy chương trình trong thời gian nhanh nhất (ít nhất giảm thời gian chạy chương trình xuống 1/2 thời gian so với chương trình trên). Trình bày rõ những kiến thức áp dụng để cải tiến giải thuật.
uses windows;
const fi='prime.inp';
fo='prime.out';
var x:int64;
f,g:text;
time:longint;
function isprime(n:int64):boolean;
var i:int64;
begin
isprime:=true;
if n<2 then
begin
isprime:=false;
exit;
end;
i:=2;
while i<=trunc(sqrt(n)) do
begin
if n mod i=0 then
begin
isprime:=false;
exit;
end;
inc(i);
end;
end;
begin
time:=gettickcount;
assign(f,fi);reset(f);
assign(g,fo);rewrite(g);
readln(f,x);
if isprime(x) then
writeln(g,1)
else
writeln(g,0);
time:=gettickcount-time;
writeln(g,time);
close(f);
close(g);
end.
Chương trình trên dùng để kiểm tra số nguyên tố: đọc từ file prime.inp số nguyên x, kiểm tra xem x có phải là số nguyên tố hay không. Nếu x là số nguyên tố thì ghi vào file prime.out số 1, ngược lại thì ghi số 0. Dòng thứ hai của file prime.out ghi thời gian chạy chương trình (tính bằng mili giây).
Nếu chạy chương trình trên để kiểm tra số nguyên tố 999999999999999989 thì sẽ hết hơn 24000 mili giây (khoảng 24 giây). Các em có thể copy chương trình và chạy thử trên máy tính của mình.
Yêu cầu: em hãy cải tiến (viết lại) hàm isprime của chương trình trên để có thể chạy chương trình trong thời gian nhanh nhất (ít nhất giảm thời gian chạy chương trình xuống 1/2 thời gian so với chương trình trên). Trình bày rõ những kiến thức áp dụng để cải tiến giải thuật.