- Ebook Giải thuật và lập trình Lê Minh Hoàng
- Các thuật toán sắp xếp trong Pascal

Kiểm tra số nguyên tổ trong pascal



Nhập vào 1 số. Xác định xem số đó có phải số nguyên tố hay không.

Đây là một bài toán rất căn bản trong Pascal. Ý tưởng: Số nguyên tố là số chia cho 1 và chính nó. Giả sử số vừa nhập vào là n, ta cho i chạy từ 2 đến n-1, nếu n chia hết cho i trong bất cứ lần lặp nào thì có nghĩa là n không nguyên tố, nếu không chia hết cho bất cứ lần lặp nào là nguyên tố. Về nguyên tắc là như vậy, nhưng người ta đã chứng minh được rằng chỉ cần xét từ 1 đến phần nguyên căn 2 của N. Như thế thuật toán sẽ tối ưu hơn.


program kiem_tra_nguyen_to;
uses crt;
var n,i:integer; bl:boolean;
begin
 clrscr;
 bl:=true;
 write('nhap vao so can kiem tra tinh nguyen to: '); readln(n);
 if n<=1 then bl:=false;
 for i:=2 to trunc(sqrt(n)) then
  if n mod i=0 then bl:=false;
 if bl=true then write('so vua nhap nguyen to.')
 else write('so vua nhap khong nguyen to.');
readln;
end.

Bouns: Chứng minh: Chỉ cần xét từ 1 đến phần nguyên căn 2 của N thay vì xét đến N: 
Lấy ví dụ số không nguyên tố:
9=3*3
12=3*4
18=2*9=3*6
20=4*5=2*10
trong các ví dụ trên, các số không nguyên tố được phân tích thành tích các cặp ước của chúng, trong mỗi cặp số nhỏ đứng trước, số lớn đứng sau. Trong mỗi cặp, ta có thể thấy rõ một điều: số đứng trước (nhỏ hơn) luôn luôn nhỏ hơn hoặc bằng căn bậc hai của số cần xét. Ví dụ ta thấy 20=4*5, rõ ràng 4 nhỏ hơn căn bậc hai của 20. Bạn tự xét các ví dụ khác nhé. Có thể chứng minh được điều này bằng toán học như sau:


Chứng minh: Gọi số cần xét là n, căn bậc hai của nó là x, hai ước tương ứng có tích bằng n của nó là a và b(a<>b), ta cần chứng minh a<x hoặc b<x. Vì a và b có vai trò tương đương, nên ta giả sử a<b.
Giả sử a>x và b>x, ta có a*b>x*x=n => trái với giải thiết. Vậy trong hai số a và b, phải có một số nhỏ hơn x. 
Dựa vào đặc điểm trên, ta sẽ giới hạn phạm vi của i là 2->n-1 thành 2->sqrt(n). Tuy nhiên, sqrt(n) với n không chính phương sẽ ra số vô tỉ, trong khi i là số nguyên, vậy cần làm tròn sqrt(n). Phạm vi mới sẽ là 2->trunc(sqrt(n)).



Nặc danh nói...

trunc(sqrt(n)) là mình làm gì với biến n vậy ?


20:36 Ngày 23 tháng 10 năm 2012
Trần Hoàng Anh nói...

trunc(sqrt(n)) là mình làm tròn cái căn bậc hai của n.


08:32 Ngày 30 tháng 10 năm 2012
Huy ding quang nói...

cái này với sô to to một tí thì thôi rồi nhất là tim trong một dãy số xem có bao nhiêu số nguyên tố


11:27 Ngày 19 tháng 11 năm 2012
Thái Hoàng Hữu nói...

for i:=2 to trunc(sqrt(n)) "then" nhờ ADMIN sửa then = do nhé :D


16:48 Ngày 27 tháng 11 năm 2012
Nặc danh nói...

lam thế nào để tính tổng căn bậc 3 của các số âm


08:43 Ngày 05 tháng 12 năm 2012
TÌNH Bạn nói...

có ai giúp mình bài này đk không :
Cho dãy số a1, a2, a3,…, aN (1<=N<=100) các phần tử là các số nguyên có giá trị tuyệt đối nhỏ hơn 32000, số N và dãy số nhập vào từ bàn phím. Hãy phân tích các phần tử dương của dãy ra thừa số nguyên tố và tìm số có tổng các số nguyên tố đã phân tích là lớn nhất, in kết quả ra màn hình.
Ví dụ
N = 5
6 11 -6 8 15
6 = 2 x 3
11 = 11
8 = 2 x 2 x 2
15 = 3 x 5
So co tong cac so nguyen to lon nhat la: 11


03:22 Ngày 09 tháng 12 năm 2012
Nặc danh nói...

Bạn giúp mình bài này với(hoặc chỉ trang có cách giải cũng được):
Nhập vào một số và chuyển thành xâu kí tự
VD: 324 thành " Ba trăm hai mươi tư"
Thanhks nhiều. Nếu bạn giúp được trong hai ngày thì tốt quá (trước 15/12/2012)


22:03 Ngày 13 tháng 12 năm 2012
Doan van Sang nói...
Nhận xét này đã bị tác giả xóa.
Doan van Sang nói...

uses crt;
var n,i,t,e:integer;
a:array [1..100] of integer;
function ktnt(a:integer):boolean;
var i:integer;
kt:boolean;
begin
kt:=true;
if a<=1 then kt:=false;
for i:=2 to trunc(sqrt(a)) do
if a mod i =0 then kt:=false;
ktnt:=kt;
end;
procedure pt(n:integer);
var j,d:integer;
m:array [1..100] of integer;
begin
d:=0;
for j:=1 to n do
if ktnt(j) then
begin
inc(d);
m[d]:=j;
end;
j:=1;
e:=0;
write(n,' = ');
while j<=d do
begin
if n mod m[j] =0 then
begin
n:=n div m[j];
write(m[j]:4);
e:=e+m[j];
end
else inc(j);
end;
writeln;
end;
begin
clrscr;
readln(n);
for i:=1 to n do
begin
writeln('a[',i,'] = ');readln(a[i]);
end;
t:=0;
for i:=1 to n do
if a[i]>1 then
begin
pt(a[i]);
if t<=e then t:=e;
end;
writeln('So co tong cac so nguyen to lon nhat la = ',t);
readln
end.


14:09 Ngày 06 tháng 01 năm 2013
Doan van Sang nói...

bài của trang nói thì phải cụ thể hơn 1 chút nếu không nó sẽ rất dài ! đó là số đó nầm trong khoảng nào !nếu số đó quá lớn giả sử 12345678967238747459474363384384..... thì mình nghĩ mọi người cũng bó tay thôi! còn nếu là số nhỏ dưới 1000 chẳng hạn thì :
b1:
+) cho 1 vòng lặp t từ 0 tới 9
.gán t[1]:='khong';
-------------
t[9]:='chin';
+) chuyển số về sâu s
.ktra xem do dai sau la bao nhieu
nếu length(s)=4 thì
cho vòng for từ 1->4 chuyển từng phần tử của sâu ->từng pt của mảng, giả sử là mảng a[i] chẳng hạn
cách đọc sẽ là t[a[1]],'nghìn',t[a[2]],'tram',t[a[3]],'muoi't[a[4]]
lưu ý : nếu vị trí cuối =0 thì 'muoi'->'mười'
nếu vị trí thứ 3=0 thì t[a[3]] ->'linh'
nếu cả 3 vị trí 2,3,4=0 thì chỉ cần t[a[1]],'nghìn'
Còn đối với length(s)=1,2,3 thì tương tự thui
chúc bạn thành công!
đây là mail của mình :doanvasang.vp@gmail.com
hoac doanvansang_vp@yahoo.com


14:41 Ngày 06 tháng 01 năm 2013
Nặc danh nói...

xam xam nhung cung hay hay


15:14 Ngày 12 tháng 01 năm 2013
Hoàng Phụng nói...

Mình nghĩ cách này sẽ nhanh hơn đấy!@@


program ktnto;
uses crt;
var n,nt,k:longint;

begin
clrscr;
write('n = ');
readln(n);
if (n = 2) or (n = 3) then nt:=0
else if (n mod 2 = 0) or (n mod 3 = 0) then nt:=1
else
begin
nt:=0;
k:=5;
while k <= trunc(sqrt(n)) do
begin
if (n mod k = 0) or (n mod (k+2) = 0) then nt:=1;
break;
k:=k+6;
end;
end;
if nt=0 then write(n,' la so nguyen to') else write(n,' khong phai la so nguyen to');
readln
end.


10:03 Ngày 18 tháng 05 năm 2013
Bảo Ngân Đặng nói...

bài này mỗi lần làm là phải mở vở ra coi đúng là khó nhớ qá!!!


10:04 Ngày 06 tháng 07 năm 2013
Nặc danh nói...

Tại sao bài tập lại không dùng hàm Round(sqrt(n))mà lại đi lấy phần nguyên?


18:12 Ngày 31 tháng 07 năm 2013
Nặc danh nói...

Tại sao bài tập lại không dùng hàm Round(sqrt(n))mà lại đi lấy phần nguyên?

Lấy phần nguyên sẽ tiết kiệm từ 0-->1 vòng lặp nhưng dùng Round cho an toàn nhưng trong một số bài toán vòng lặp của nó còn nhiều vòng lặp nữa nên tiết kiêm 1 vòng = time


18:20 Ngày 08 tháng 11 năm 2013
Linh Trịnh nói...

cac ban kiem tra dum minh doan chuong trinh nay sai cho nao vay?
begin
assign(f,'d:\in.txt');
assign(f1,'d:\out.txt');
reset(f);
rewrite(f1);
readln(f,n);
for i:=1 to n do
begin
read(f,a[i]);
t:=trunc(sqrt(a[i]));
for i:=1 to t do
begin
if (a[i] mod i =0) and ( i=t) then writeln(f1,' la so nguyen to')
else write( f1 , ' khong phai la so nguyen to ' );
close (f);
close(f1);
end.


12:35 Ngày 03 tháng 04 năm 2014
Nặc danh nói...

Hay , cam on


00:48 Ngày 02 tháng 05 năm 2014
Nặc danh nói...

program snt;
uses crt;
var i,n:integer;
begin
clrscrl;
write('nhap n:');
readln(n);
i:=2;
while n mod i<>0 do i:=i+1;
if i=n then write('la so nguyen to')
else write('khong la s nguyen to');
readln;
end.


14:54 Ngày 02 tháng 07 năm 2014

Đăng nhận xét

Thành viên Blog

Tổng số lượt xem trang

Translate

Return to top of page Copyright © 2012 | Theme by Hack Tutors. Cung cấp bởi Blogger.
Các code pascal trong blog được sưu tầm, lựa chọn sao cho tối ưu nhất. Cảm ơn các tác giả đã viết thuật toán.