[정수론] 오일러피

✔ 오일러 피

오릴러 피란?

1부터 N까지 범위에서 N과 서로소인 자연수의 개수

서로소란?

공약수가 1 이외에 존재하지 않는 것

오일러 피 함수의 원리

1. 구하고자 하는 오일러 피의 범위만큼 배열을 초기화
2. 2부터 시작해 현재 배열의 값과 인덱스가 같으면 (소수일 때)
   현재 선택된 숫자의 배수에 해당하는 수를 배열 끝까지 탐색하며 P[i] = P[i] - P[i]/K 연산을 수행
   • 예) P[6]
   • 서로소가 될 수 있는 후보의 개수로 초기화 : P[6] = 6 (1, 2, 3, 4, 5, 6)
   • 2의 배수로 인한 후보 탈락 : P[6] = 6 - (6 / 2) = 3 (1, 3, 5)
   • 3의 배수로 인한 후보 탈락 : P[6] = 3 - (3 / 3) = 2 (1, 5)
3. 배열의 끝까지 위를 반복하여 오일러 피 함수를 완성

 

Do it! 알고리즘 코딩테스트 with JAVA

https://inf.run/w9Tn