반응형
출처: https://www.acmicpc.net/problem/4355
Input
7
12
0
Output
6
4
오일러 피(파이) 함수(Euler's phi function)
오일러 피(파이) 함수 ϕ(n) 1~n까지의 수 중에서 n과 서로소인 수의 갯수 ※ 서로소 관계: 두 수 a, b의 공약수가 1뿐인 두 정수를 의미한다. ϕ(1) = 1 (1은 1과 서로소) ϕ(8) = { 1, 3, 5, 7 } =..
zoosso.tistory.com
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
while(true) {
int N = Integer.parseInt(br.readLine());
if(N == 0) break;
bw.write(EulerPhi(N) + "\n");
}
bw.flush();
bw.close();
}
private static long EulerPhi(int n) {
long ret = n;
for (long i = 2; i * i <= n; i++) {
if (n % i == 0) {
while (n % i == 0) {
n /= i;
}
ret -= ret / i;
}
}
if (n > 1) {
ret -= ret / n;
}
return ret;
}
}
반응형
'PS 문제 풀이 > Baekjoon' 카테고리의 다른 글
[BOJ] 백준 1708 블록 껍질 (0) | 2021.02.22 |
---|---|
[BOJ] 백준 17135 캐슬 디펜스 (0) | 2021.02.22 |
[BOJ] 백준 17406 배열 돌리기 4 (0) | 2021.02.22 |
[BOJ] 백준 1786 찾기 (0) | 2021.02.22 |
[BOJ] 백준 1120 문자열 (0) | 2021.02.22 |
댓글