- 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 23 tháng 10, 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 30 tháng 10, 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 19 tháng 11, 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 27 tháng 11, 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 5 tháng 12, 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 9 tháng 12, 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 13 tháng 12, 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 6 tháng 1, 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 6 tháng 1, 2013
Nặc danh nói...

xam xam nhung cung hay hay


15:14 12 tháng 1, 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 18 tháng 5, 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 6 tháng 7, 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 31 tháng 7, 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 8 tháng 11, 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 3 tháng 4, 2014
Nặc danh nói...

Hay , cam on


00:48 2 tháng 5, 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 2 tháng 7, 2014
Nguyễn Rise nói...

giải giúp mk bài : nhập một số n tìm số nguyên tố nhỏ nhất lớn hơn n


10:05 14 tháng 4, 2015
Trần Trí nói...

mình k hiểu đoạn này , ai jup vs , for i:=2 to trunc(sqrt(n)) tại sao phải cho chạy dén phần nguyên căn của n vậy


11:34 23 tháng 8, 2015
hieu truong nói...

thank you very much


08:59 9 tháng 11, 2015
Unknown nói...

số được sắp xếp hợp lí các chữ số của nó thì là số nguyên tố . số đó gọi là số gần nguyên tố , giúp mình với


20:56 8 tháng 3, 2016
Hồng Hạnh Nguyễn Thị nói...

giải giúp mình bà con
viết chương trình in ra màn hình số đẹp
đúng mình sẽ hậu tạ
mình cần gấp


20:36 31 tháng 3, 2016
Hồng Hạnh Nguyễn Thị nói...

viết chương trình in ra màn hình số phong tố


20:37 31 tháng 3, 2016
Dang Tho nói...

thế nếu muốn kiểm tra xem trong các số vừa nhập có những ố nào là số nguyên tố thì giải sao


20:40 12 tháng 5, 2016
Dang Tho nói...

thế nếu muốn kiểm tra xem trong các số vừa nhập có những ố nào là số nguyên tố thì giải sao


20:42 12 tháng 5, 2016
son samso nói...

lệnh truc(...) đc dùng khi nào mấy bạn


21:00 25 tháng 10, 2016
Nặc danh nói...

fuck pascal


10:17 3 tháng 11, 2016
hoang yen nguyen nói...

giup minh lam bai tinh tong cac so nguyen to nho hon n


07:54 26 tháng 11, 2016
Unknown nói...

Giúp mình với.nhập nguyên dương n. Thy dổi vị trí một chữ số bất kỳ trong n để số đó là số lớn nhât


09:34 28 tháng 11, 2016
Tuyen Tran nói...

Nhập số nguyên dương n.thay đởi vị trí một chữ số bất kỳ sao cho sió đó là số lớn nhất


09:36 28 tháng 11, 2016
vũ hoàng nói...

bạn so sánh các chữ số trong số đó rồi sắp xếp lại, số nào lớn hơn thì đứng trước. dùng phương pháp nổi bọt ấy.


20:22 2 tháng 12, 2016
sơn Hoàng nói...
Nhận xét này đã bị tác giả xóa.
sơn Hoàng nói...

nho ban thay then=do


21:55 11 tháng 1, 2017
Unknown nói...

uses crt;
var n,i:integer;
begin
clrscr;
write('nhap n: ');readln(n);
for i:=1 to n do
if i mod 2<> 0 then
write('cac so nguyen to la ',i);
readln;
end.


20:12 17 tháng 1, 2017
Nặc danh nói...

ga vl


20:10 13 tháng 3, 2017
Nặc danh nói...

ai giúp với bài này:nhập vào một số ,nếu đó là số nguyên tố thì đảo ngược.
làm dơn giản nhé


20:28 14 tháng 3, 2017
Nặc danh nói...

Viết chương trình nhận biết một số tự nhiên n đc nhập vào từ bán phím có phải là số nguyên tố hay không


19:46 24 tháng 3, 2017
Nặc danh nói...

WTF?


22:21 26 tháng 3, 2017
Nặc danh nói...

Hướng dẫn toàn mấy cái xàm xàm ba láp


22:24 26 tháng 3, 2017
Unknown nói...

Hướng dẫn tốt!!!


00:15 15 tháng 4, 2017

Đă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.