https://www.acmicpc.net/problem/4355
void countCoPrime(int n) {
int[] arr = new int[n+1];
for (int i = 1; i < arr.length; i++) {
arr[i] = i;
}
for (int i = 2; i <= n; i++) { // 자꾸 2부터 시작해야한다는 걸 까먹는다..! 2부터 시작
if(arr[i] == i){
for (int j = i; j <= n; j += i) {
arr[j] = arr[j] - (arr[j] / i);
}
}
}
System.out.println(arr[n]);
}
int eulerPhi(int n) {
int[] arr = new int[n + 1];
for (int i = 1; i < n + 1; i++) {
arr[i] = i;
}
for (int i = 2; i < n + 1; i++) {
if (arr[i] == i) {
for (int j = i; j < n + 1; j += i) {
arr[j] = arr[j] - (arr[j] / i);
}
}
}
for (int i = 1; i < n + 1; i++) {
System.out.println(arr[i]);
}
System.out.println("------------------");
return arr[n];
}