Bài tập về số nguyên tố, số siêu nguyên tố, số nguyên tố tương đương, số phản nguyên tố.

Bài 1. Phân tích số nguyên dương N thành tích của các thừa số nguyên tố.

VD: 12 = 2*2*3

Chương trình

uses crt;

var i,j,n:longint;

a:array[2..100000] of longint;

f1,f2:text;

begin

assign(f1,'bai1.inp');reset(f1);

assign(f2,'bai1.out');rewrite(f2);

readln(f1,n);

i:=2;a[2]:=0;

while n<>1 do

begin

while n mod i <> 0 do

begin

i:=i+1;

a[i]:=0;

end;

a[i]:=a[i] +1;

n:=n div i;

end;

for j:=2 to i do if a[j] > 0 then writeln(f2,j,' ',a[j]);

close(f1);close(f2);

end.

Bài 2. Số nguyên tố tương đương.Hai số tự nhiên được gọi là nguyên tố tương đương nếu chúng có cùng các ước số nguyên tố. Ví dụ 75 và 15 là nguyên tố tương đương vì cùng có các ước nguyên tố là 3 và 5. Cho trước hai số tự nhiên a và b. Hãy viết chương trình kiểm tra xem 2 số này có là nguyên tố tương đương với nhau hay không?

Chương Trình

uses crt;

var

f1,f2:text;

a:array [1..100] of integer;

i,k,m,n:integer;

Begin

assign(f1,'bai2.inp');reset(f1);

assign(f2,'bai2.out');rewrite(f2);

Readln(f1,m,n);

if m<n then begin k:=m;m:=n;n:=k;end;

i:=1;k:=0;

Repeat

i:=i+1;

if (m mod i=0) and (n mod i=0) then

begin

if k=0 then

Writeln(f2,'co');

While (m mod i=0) and (n mod i=0) do

begin

m:=m div i;n:=n div i;

end;

Until i>=n;

if k=0 then

Writeln('ko');

close(f1);close(f2);

End.

Bài 3. Số siêu nguyên tốSố siêu nguyên tố là số nguyên tố mà khi xoá bỏ dần các chữ số bên phải của nó thì phần còn lại vẫn là số nguyên tó. Ví dụ 2333 là số siêu nguyên tó vì 2333, 233, 23 ,2 đều là số nguyên tố.Yêu cầu: Cho số nguyên dương M (M <= 30000). Hãy sìm số siêu nguyên tố gần với M nhất tức là trị tuyệt đối của hiệu giữa số tìm được với M là nhỏ nhất)Dữ liệu vào: Nhập vào từ bàn phím số nguyên dương M (không cần kiểm tra dữ liệu nhập).Dữ liệu ra: Ghi ra màn hình hai số siêu nguyên tố gần M nhất, mỗi số một dòng theo thứ tự số nhỏ hơn ghi trước.

Ví dụ:

Dữ liệu nhập: 30

Kết quả in ra trên 2 dòng:

Chương trình

PROGRAM sieunguyento;

USES crt;

VAR j,i:longint;

M:longint;

f1,f2:text;

{---------------------------------------------------------------------}

FUNCTION snt(n:integer):boolean;

var

nt:boolean;

j:integer;

begin

nt:=true;

if (n<2) then nt:=false;

for j:=2 to n-1 do if n mod j = 0 then nt:=false;

snt:=nt;

end;

function sieunt(n:integer):boolean;

var nt:boolean;

i:integer;

begin

nt:=true;

while snt(n) do n:=n div 10;

if n<>0 then nt:=false;

sieunt:=nt;

end;

{---------------------------------------------------------------------}

BEGIN

assign(f1,'sieunguyento.inp');reset(f1);

assign(f2,'sieunguyento.out');rewrite(f2);

readln(f1,M);

for i:=M-1 downto 2 do

if sieunt(i)=true then

begin

writeln(f2,i);

break;

end;

for j:=M+1 to 30000 do

if sieunt(j)=true then

begin

write(f2,j);

break;

end;

close(f1);close(f2);

END.

Bài 4. Số nguyên tố ( Năm 08 – 09).Cho dãy số gồm có n số nguyên dương a1, a2, ..., an và một số nguyên dương k.Yêu cầu: Hãy cho biết số lượng các phần tử có giá trị nhỏ hơn k là số nguyên tố của dãy số trên.Dữ liệu : Vào từ file Bai1.inp gồm: Dòng đầu tiên là hai số n và k. Dòng tiếp theo lần lượt là n số nguyên của dãy số.Kết quả: Ghi ra file bai1.out gồm duy nhất số m là số lượng các phần tử của dãy số thoả mãn yêu cầu đề bài.Giới hạn: 0 < n < 50000; 0 < k, ai < 5000

Chương Trình

uses crt;

var a:array[1..50000] of longint;

k,m,i,j,n:longint;

f1,f2:text;

function KiemtraSNT(N:integer):boolean;

Var nt: Boolean;

i:Integer;

Begin

nt:= True;

if N=1 then nt:=false;

For i := 2 to N-1 do

If ( N mod i = 0 ) then

nt:=false;

KiemtraSNT:=nt;

End;

BEGIN

assign(f1,'bai4.inp');reset(f1);

assign(f2,'bai4.out');rewrite(f2);

readln(f1,n,k);

m:=0;

while not eof(f1) do

for i:= 1 to n do

begin

read(f1,a[i]);

KiemtraSNT(a[i]);

if (KiemtraSNT(a[i])=true) and ( a[i] < k ) then inc(m);

end;

write(f2,m);

close(f1);close(f2);

end.

Bài 5. Số nguyên tố. Cho dãy số gồm có N số nguyên a1, a2, ..., aN và một số nguyên K.Yêu cầu: Hãy cho biết chỉ số và giá trị cả các phần tử có giá trị nhỏ hơn K là số nguyên tố.Dữ liệu : Vào từ filư văn bản bai1.inp gồm:
Dòng đầu tiên là hai số N và K Dòng tiếp theo lần lượt là N số nguyên của dãy sốKết quả: Ghi ra file bai1.out gồm:
Dòng đầu tiên là số M là số lượng các phần tử của dãy số là số nguyên tố. Nếu M > 0 thì M dòng tiếp theo, mỗi dòng ghi chỉ số và giá trị của một phần tử thuộc dãy số thoả mãn yêu cầu đề bài.Giới hạn: 0 < N < 1000; 0 < k, < ai < 1000

Ví dụ

Bai1.inp Bai1.out

7 8 2

1 3 7 6 11 13 8 2 3

3 7

Chương Trình

uses crt;

var a:array[1..50000] of longint;

k,m,i,j,n:longint;

f1,f2,f3:text;

function ktsnt(N:integer):boolean;

Var nt: Boolean;

i:Integer;

Begin

nt:= True;

if N<2 then nt:=false;

For i := 2 to N-1 do

If ( N mod i = 0 ) then

nt:=false;

ktsnt:=nt;

End;

BEGIN

assign(f1,'bai5.inp');reset(f1);

assign(f2,'bai5.out');rewrite(f2);

assign(f3,'trunggian.inp');rewrite(f3);

read(f1,n,k);

m:=0; j:=0;

while not eof(f1) do

for i:=1 to n do

begin

read(f1,a[i]);j:=j+1;

if (ktsnt(a[i])) and ( a[i] < k ) then

begin

m:=m+1;;

writeln(f3,j,' ',a[i]);

end;

close(f1); close(f3);reset(f3);

writeln(f2,m);

for i:=1 to m do begin

readln(f3,j,a[i]);

writeln(f2,j,' ', a[i]);

end;

close(f2);close(f3);

end.

Bài 6. Số nguyên tố (Bài 5_ 09- 10)Số nguyên tố là số chỉ có thể chia hết cho 1 và chính nó.Giả xử dãy A là một dãy tăng dần các số nguyên tố 2, 3, 5, 7, 11, 13, …

Ta lập dãy B bằng cách viết ghép từng cặp số nguyên tố liền kề nhau: 23, 57, 1113, …

C là dãy nhận được từ B bằng cách loại đi các số không phải là số nguyên tố.Hãy tìm N số hạng đầu của dãy C với (0 < N <= 300).Dữ liệu: Vào từ file văn bản Bai5.Inp: Chứa số nguyên dương N.Kết quả: Ghi ra file văn bản Bai5.Out: Gồm N dòng, mỗi dòng chứa một số thuộc dãy C.

Ví dụ

Bai5.Inp Bai5.Out

3137

8389

157163

167173

Chương Trình

uses crt;

const nmax=1e6;

var a,b,c:array[1..10000] of longint;

k,m,e,d,N,i,j:longint;

s1,s2,S:string;

function KTSNT(n:longint):boolean;

var i:longint;

begin

KTSNT:=false;

if n=2 then ktsnt:=true;

if n < 2 then exit;

i:=2;

while i*i <= n do

begin

if n mod i = 0 then exit;

inc(i);

end;

KTSNT:=true;

end;

{--------------------------------------------------}

procedure gangiatri;

Begin

i:=1;

for j:=2 to 1000 do

begin

if KTSNT(j) then

begin

a[i]:=j;

inc(i);

end;

m:=1;k:=1;

for k:=1 to 300 do

begin

str(a[m],S1);

str(a[m+1],S2);

val(S1+S2,b[k]);

inc(m,2);S1:='';S2:='';

end;

e:=1;

for d:=1 to 100 do

if KTSNT(b[d]) then

begin

c[e]:=b[d];

inc(e);

end;

End;

end;

{-------------------------------------------------}

BEGIN

clrscr;

write('nhap so n: ');readln(N);

gangiatri;

for i:=1 to N do writeln(c[i]);

readln

END.

Bài 7. Số phản nguyên tố.Một số n gọi là số phản nguyên tố nếu số ước số của nó là nhiều nhất trong n nguyên dương đầu tiên. Cho số k. Hãy ghi ra số phản nguyên tố lớn nhất nhỏ hơn hoặc bằng K.

Dữ liệu vào trong file PNT.inp nội dung gồm: Dòng đầu tiên là số M (1 < M <= 100)
M dòng tiếp theo lần lượt là các số k1, k2, ..., km;Dữ liệu ra trong file PNT.out gồm M dòng: dòng thứ i là số phản nguyên tố lớn nhất nhỏ hơn hoặc bằng Ki.

Giới hạn: 0 < ki < 2000000;

Ví dụ:

PNT.inp PNT.out

1 840

1000

Chương Trình

var a:array[1..20000]of longint;

i,j,n,m:longint;

f1,f2:text;

{-----------------------------------------------}

function tinhuoc(n:longint):longint;

var m:longint;

begin

m:=0;

for i:=1 to n do if n mod i = 0 then inc(m);

tinhuoc:=m;

end;

{-----------------------------------------------}

function pnt(n:longint):longint;

var chiso:longint;

begin

m:=0;

for i:=1 to 1000 do

begin

a[i]:=tinhuoc(i);

if m<=a[i] then

begin

m:=a[i];

chiso:=i;

end;

pnt:=chiso;

end;

{----------------------------------------------}

begin

assign(f1,'PNT.INP');reset(f1);

assign(f2,'PNT.OUT');rewrite(f2);

readln(f1,n);

for i:=1 to n do

begin

readln(f1,a[i]);

if pnt(a[i])<>0 then writeln(f2,pnt(a[i]));

end;

close(f1);close(f2);

end.

Bài Tập Pascal Tổng Hợp