백준 - GCD(n, k) = 1 (11689)

import Foundation

var n = Int(readLine()!)!
var result = n

for i in stride(from: 2, through: Int(Double(n).squareRoot()), by: 1) {
    if n % i == 0 { // i가 n의 소인수이면
        result = result - (result / i)
        while n % i == 0 { // n에서 현재 소인수 삭제
            n /= i
        }
    }
}

if n > 1 { // 남은 소인수가 있는 경우 결과 업데이트
    result = result - (result / n)
}

print(result)

• 오일러 피 함수를 사용하여 1 ≤ k ≤ n인 서로소 개수를 구한다.
• n의 소인수(소수이자 n의 약수)라면 오일러 피 함수를 사용하여 결과값을 업데이트한다.
  • 이때 나누기 연산을 통해 n에서 현재 소인수를 삭제한다.
  • 반복문을 벗어난 후에 n > 1이라면 소인수가 남아있다는 뜻이다. 따라서 남은 소인수를 가지고 결과값을 계산한 후 출력한다.