- 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 ?


lúc 20:36 23 tháng 10, 2012
Unknown nói...

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


lúc 08:32 30 tháng 10, 2012
Unknown 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ố


lúc 11:27 19 tháng 11, 2012
Unknown nói...

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


lúc 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


lúc 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


lúc 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)


lúc 22:03 13 tháng 12, 2012
Unknown nói...
Nhận xét này đã bị tác giả xóa.
Unknown 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.


lúc 14:09 6 tháng 1, 2013
Unknown 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


lúc 14:41 6 tháng 1, 2013
Nặc danh nói...

xam xam nhung cung hay hay


lúc 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.


lúc 10:03 18 tháng 5, 2013
Unknown nói...

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


lúc 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?


lúc 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


lúc 18:20 8 tháng 11, 2013
Unknown 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.


lúc 12:35 3 tháng 4, 2014
Nặc danh nói...

Hay , cam on


lúc 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.


lúc 14:54 2 tháng 7, 2014
Unknown 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


lúc 10:05 14 tháng 4, 2015
Tri Tran 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


lúc 11:34 23 tháng 8, 2015
Unknown nói...

thank you very much


lúc 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


lúc 20:56 8 tháng 3, 2016
Unknown 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


lúc 20:36 31 tháng 3, 2016
Unknown nói...

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


lúc 20:37 31 tháng 3, 2016
Unknown 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


lúc 20:40 12 tháng 5, 2016
Unknown 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


lúc 20:42 12 tháng 5, 2016
Unknown nói...

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


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

fuck pascal


lúc 10:17 3 tháng 11, 2016
Unknown nói...

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


lúc 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


lúc 09:34 28 tháng 11, 2016
Unknown 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


lúc 09:36 28 tháng 11, 2016
Unknown 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.


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

nho ban thay then=do


lúc 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.


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

ga vl


lúc 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é


lúc 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


lúc 19:46 24 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


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

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


lúc 00:15 15 tháng 4, 2017
Unknown nói...

Dài vc t lm ngắn hơn nhiều:
Uses crt;
var n,i:integer;
begin
clrscr;
readln(n);
i:=2;
while n mod i<>0 do i:=i+1;
if i=n then write('la so nguyen to') else write('ko phai la so nguyen to');
readln
end.


lúc 19:56 16 tháng 11, 2017
Unknown nói...

Tại sao khi kiểm tra lại dùng căn bậc hai vậy ạ?


lúc 21:25 29 tháng 1, 2018
Nặc danh nói...

cách này vẫn chưa là cách tối ưu dùng biến boolean theo kiểu đúng sai thì nó sẽ đúng trong mọi trường hợp mọi người theo làm theo kiểu này để có chất lượng đúng nhất đây là thuật toán bài này của mình
for i:=2 to n-1 do ì n mod i=0 then ok:=false
if ok then write(k,' la so.......)


lúc 19:40 26 tháng 2, 2018
Unknown nói...

là phần nguyên của √n nha bạn


lúc 19:19 14 tháng 3, 2018
Unknown nói...

Thuật toán này đúng ko vậy!!
Program SNT;
Uses crt;
Var n , i :Integer; // Khai bao bien su dung
BEGIN
Write(‘Nhap vao mot so:’); // Thong bao nhap lieu
Readln(n); // Nhap gtri N, (voi &N la lay d/c bien N)
i := round( sqrt(n) );
If( n mod i <> 0) then // Xuat cau tra loi cuoi cung
Writeln(‘ N la so nguyen to’)
Else
Writeln(‘ N khong la so nguyen to’);
Readln;
END.
Help me please!!!!!!


lúc 18:47 14 tháng 1, 2019
Unknown nói...

function snt(n:int64):boolean;
var k:longint;
begin
if (n = 2) or (n = 3) then exit(true);
if (n mod 2 = 0) or (n mod 3 = 0) then exit(false);
k:=5;
while k <= trunc(sqrt(n)) do
begin
if (n mod k = 0) or (n mod (k+2) = 0) then exit(false) else
k:=k+6;
end;
exit(true);
end;
var n:int64;
mấy má nè
begin
readln(N);
if snt(N)=true then write(N);
end


lúc 21:30 13 tháng 3, 2019
Unknown nói...

Bằng round() phải ko bạn


lúc 22:22 11 tháng 4, 2019
Flash nói...
Nhận xét này đã bị tác giả xóa.
Unknown nói...

giúp mik bài này vs ạ:viết chương trình pascal tìm ra cặp số nguyên tố có tổng bằng n, nếu có nhiều cặp thì hãy lấy cặp có số nguyên tố nhỏ nhất


lúc 10:45 9 tháng 2, 2020
Unknown nói...

=)) vl 2 ong nhan tu 2012 toi tan 2021 a :))


lúc 16:22 7 tháng 1, 2022

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