#5345. Euler Totient Function Sieve (Mã bài : ETFS)

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Trùm CUỐI

Đề bài

Hàm phi Euler \phi(n) được định nghĩa là số các số nguyên dương nhỏ hơn hoặc bằng n và nguyên tố cùng nhau với n .

Yêu cầu: Cho hai số nguyên a b , hãy tính và in ra giá trị \phi(i) cho tất cả các số i từ a đến b .

Dữ liệu: Một dòng duy nhất chứa hai số nguyên a b .

Kết quả: In ra các giá trị \phi(i) cho i = a, a+1, \dots, b , mỗi giá trị trên một dòng.

Ví dụ:

Dữ liệu:

1 5

Kết quả:

1
1
2
2
4

Giới hạn:

  • 1 \le a \le b \le 10^6
  • b - a \le 10^5