Số những số nguyên tố cùng nhau
Submit solution
Points:
2 (partial)
Time limit:
2.0s
Memory limit:
98M
Author:
Problem type
Allowed languages
Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG
Hai số nguyên dương a và b được gọi là nguyên tố cùng nhau nếu ước chung lớn nhất của chúng bằng 1. Cho số nguyên dương n hãy đếm những số nguyên dương trong đoạn [1,n] nguyên tố cùng nhau với n
Input
Dòng đầu là số bộ test \(t (1 \leq t \leq 10^4)\)
Tiếp theo gồm \(t\) dòng mỗi dòng chứa đúng một số nguyên dương \(n (1 < n \leq 10^9)\)
Output
Gồm \(t\) dòng mỗi dòng chứa đúng một số nguyên dương là số những số nguyên dương nhỏ hơn \(n\) nguyên tố cùng nhau với \(n\)
Ví dụ
Input
2
9
10Output
6
4Giải thích
Với \(n = 9\) có 6 số nguyên tố cùng nhau với 9 trong đoạn [1,9] là \(1,2,4,5,7,8\)
Với \(n = 10\) có 4 số nguyên tố cùng nhau với 10 trong đoạn [1,10] là \(1,3,7,9\)
Comments
Hàm Phi Euler