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

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *