Cặp số nguyên tố cùng nhau

Xem dạng PDF

Gửi bài giải

Điểm: 100,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout

Người đăng:
Dạng bài

Cho số nguyên N, hãy tìm số lượng các số nguyên dương X nhỏ hơn N thỏa mãn: XN2 số nguyên tố cùng nhau. (Tức là UCLN của XN bằng 1)

Input

  • Một dòng duy nhất là số nguyên N(N2109),

Output

  • Số lượng các số nguyên dương X

Scoring

  • Subtask 1 (50% số điểm): 2N20000.
  • Subtask 2 (40% số điểm): 20000N2106.
  • Subtask 3 (10% số điểm): 2106N2109

Ví dụ

Input
Copy
5
Output
Copy
4

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.