P152PROA PTIT SPOJ - ROUND 2A - Nguyên tố cùng nhau

Nguồn đề bài: http://www.spoj.com/PTIT/problems/P152PROA/

1. Đề bài P152PROA SPOJ

Juggernaut được cô giáo Disruptor dạy toán, cô giáo định nghĩa một hàm f(x) như sau:

Với t là số lượng các số tự nhiên k (1 <= k <= x) thỏa mãn nguyên tố cùng nhau với x, nếu t là nguyên tố thì f(x) = 1, ngược lại f(x) = 0.

Disruptor cho Juggernaut một số nguyên dương x, yêu cầu anh cho biết giá trị của hàm f(x), nếu trả lời sai thì Jug sẽ bị cô trả về nhà, Jug không muốn về nhà, các bạn hãy giúp Jug giải bài toán này.

Input

Dòng đầu tiên chứa số bộ test T (T <= 10).

Mỗi test gồm một dòng chứa số x (1 <= x <= 10^5).

Output

In ra kết quả mỗi test trên một dòng là giá trị của hàm f(x).

Example

Input:
2
2
3
Output:
0
1

2. Giải thích khái niệm P152PROA SPOJ

– Nguyên tố cùng nhau của 2 số a và b là UCLN của a và b bằng 1

Hướng dẫn:

– Xây dựng hàm UCLN, Kiểm tra số nguyên tố rồi thực hiện duyệt bình thường.

ĐPT: O(n*T)

3. code tham khảo P152PROA SPOJ

const   fi='';
type    data=longint;
var
        T,N,i,j,dem,k:data;
        snt:boolean;
        f:text;

function ktsnt(x:data):data;
var     i:data;
begin
        if x=1 then exit(0);
        for i:=2 to trunc(sqrt(x)) do
                if x mod i=0 then
                        exit(0);
        exit(1);
end;

function UCLN(a,b:data):data;
var
        r:data;
begin
        while a mod b<>0 do
                begin
                        r:=a mod b;
                        a:=b;
                        b:=r;
                end;
        exit(b);
end;

begin
        assign(f,fi); reset(f);
        readln(f,T);
        for i:=1 to T do
                begin
                        readln(f,k);
                        dem:=0;
                        for j:=1 to k do
                                if ucln(k,j)=1 then
                                        inc(dem);
                        writeln(ktsnt(dem));
                end;
        close(f);
end.

P152PROA PTIT SPOJ – ROUND 2A – Nguyên tố cùng nhau