Time Limit: 1s
Memory Limit: 128MB
두 수의 최대공약수가 1인 것을 서로소라고 한다.
1이상 n이하의 수 중 n과 서로소인 정수의 갯수를 구해보자.
Line 1: 입력의 갯수 N (1≤N≤1000)
Line 2~N+1: 자연수 n (1≤n≤10000)
1~N: n과 서로소면서 n을 넘지 않는 양의 정수 갯수를 출력한다.
3 24 36 47
8 12 46
빠르게 푸는 방법이 궁금하다면 오일러파이 함수에 대해 알아봅시다