C11PRIME spoj - Số nguyên tố

Nguồn đề bài: http://vn.spoj.com/problems/C11PRIME/

Nội dung bài viết

1. Đề bài C11PRIME spoj
2. code tham khảo C11PRIME

1. Đề bài C11PRIME spoj

Số nguyên tố là số chỉ chia hết cho 1 và chính nó. Trong một buổi dã ngoại của trường, bất ngờ TMB bị thầy giáo đố một câu như sau: “Một số có dạng p^q là lũy thừa cao của một số nguyên tố khi và chỉ khi p là một số nguyên tố và q > 1. Thầy sẽ cho em một số N bất kỳ và em hãy cho biết đó có phải là lũy thừa cao của một số nguyên tố hay không?”. Không phải lúc nào cũng mang theo máy tính bên mình, đây là lúc TMB cần bạn.

Yêu cầu: Cho số N, hãy giúp TMB trả lời câu đố của thầy giáo, nếu N là lũy thừa cao của một số nguyên tố thì in ra 2 số p và q tương ứng, nếu không thì ghi 0.

Giới hạn:

n <= 10^18

Input:

1 dòng duy nhất chứa n

Output:

1 dòng duy nhất là kết quả

Ví dụ:

Input	Output
27	3 3

Input	Output
10	0

2. code tham khảo C11PRIME

const   fi='';
        vc=high(int64);
        du=1000000000000000000;
type    data=longint;
        data1=int64;
var
        N:data1;
        f:text;

function KTSNT(n:data1):boolean;
var
        i:data;
begin
        for i:=2 to trunc(sqrt(n)) do
                if n mod i=0 then
                        exit(false);
        exit(true);
end;

function tinhcan(a:int64; b:data1):int64;
begin
        tinhcan:=round(exp(ln(a)/b));
end;

function amuk(a:int64; k:data):int64;
var     i:data;
        res:int64;
begin
        res:=1;
        for i:=1 to k do
                begin
                        res:=(res*a) mod du;
                end;
        exit(res);
end;

procedure xuli;
var     i,j:data;
        so:data1;
begin
        for i:=2 to 60 do
                begin
                        so:=tinhcan(n,i);

                        if (amuk(so,i)=n) and ktsnt(so) then
                                begin
                                        writeln(so,' ',i);
                                        exit;
                                end;
                end;
        writeln(0);
end;

begin
        assign(f,fi); reset(f);
        readln(f,n);
        close(f);
        xuli;
end.

const fi='';

vc=high(int64);

du=1000000000000000000;

type data=longint;

data1=int64;

var

N:data1;

f:text;

function KTSNT(n:data1):boolean;

var

i:data;

begin

for i:=2 to trunc(sqrt(n)) do

if n mod i=0 then

exit(false);

exit(true);

end;

function tinhcan(a:int64; b:data1):int64;

begin

tinhcan:=round(exp(ln(a)/b));

end;

function amuk(a:int64; k:data):int64;

var i:data;

res:int64;

begin

res:=1;

for i:=1 to k do

begin

res:=(res*a) mod du;

end;

exit(res);

end;

procedure xuli;

var i,j:data;

so:data1;

begin

for i:=2 to 60 do

begin

so:=tinhcan(n,i);

if (amuk(so,i)=n) and ktsnt(so) then

begin

writeln(so,' ',i);

exit;

end;

writeln(0);

end;

begin

assign(f,fi); reset(f);

readln(f,n);

close(f);

xuli;

end.

C11PRIME spoj – Số nguyên tố

1. Đề bài C11PRIME spoj

2. code tham khảo C11PRIME

Bài viết liên quan

Trả lời Hủy