문제 링크

<aside> 💡 오일러 피 함수/수학/밀러–라빈 소수 판별법/정수론/폴라드 로/소수 판정

</aside>

Memory 117344KB Time 160ms Code Length 1607B

import random, sys
input = sys.stdin.readline

def power(x, y, mod):
    x %= mod
    ret = 1
    while y > 0:
        if y % 2 == 1:
            ret = (ret * x) % mod
        x = (x * x) % mod
        y //= 2
    return ret

def check_prime(n, a):
    if a % n == 0:
        return True
    k = n - 1
    while True:
        temp = power(a, k, n)
        if temp == n - 1:
            return True
        if k % 2 == 1:
            return temp == 1 or temp == n - 1
        k //= 2

def is_prime(n):
    if n == 2 or n == 3:
        return True
    if n % 2 == 0:
        return False

    a = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
    for ai in a:
        if not check_prime(n, ai):
            return False
    return True

def gcd(a, b):
    while b != 0:
        r = a % b
        a = b
        b = r
    return a

def find_div(n):
    if n % 2 == 0:
        return 2
    if is_prime(n):
        return n

    x = random.randint(2, n-2)
    y = x
    c = random.randint(1, 10)
    g = 1
    while g == 1:
        x = (x*x + c) % n
        y = (y*y + c) % n
        y = (y*y + c) % n
        g = gcd(abs(x-y), n)
        if g == n:
            return find_div(n)
    if is_prime(g):
        return g
    else:
        return find_div(g)

N = int(input())
temp = N
if N == 1:
    print(N)
else:
    lst = []
    while N > 1:
        div = find_div(N)
        lst.append(div)
        N //= div

    lst.sort()

    ans = temp
    ans = ans // lst[0] * (lst[0] - 1)
    for i in range(1, len(lst)):
        if lst[i] != lst[i-1]:
            ans = ans // lst[i] * (lst[i] - 1)

    print(ans)

이 코드는 주어진 숫자 N의 오일러 피(phi) 함수 값을 계산하는 코드이다.

오일러 피 함수란, 어떤 자연수 N에 대해 N과 서로소인 1 이상 N 이하의 자연수의 개수를 나타내는 함수이다.

먼저, power 함수는 제곱 연산을 빠르게 처리하기 위한 함수이다. 이 함수는 x의 y 제곱을 mod로 나눈 나머지를 계산한다.

check_prime 함수는 주어진 숫자 n이 소수인지 확인하는 함수이다.

is_prime 함수는 주어진 숫자 n이 소수인지 확인하는 함수이다. 이 함수는 2부터 37까지의 소수를 이용하여 n이 소수인지 판별한다.

gcd 함수는 두 수 a와 b의 최대공약수를 찾는 함수이다.

find_div 함수는 주어진 숫자 n의 약수를 찾는 함수이다. 이 함수는 소수를 찾아 반환하거나, 소수가 아닌 경우 재귀적으로 약수를 찾는다.

마지막으로, 오일러 피 함수의 값을 계산하기 위해 주어진 숫자 N을 소인수분해하고, 각 소인수 p에 대해 N을 p로 나눈 후 (p-1)을 곱하는 과정을 반복한다. 이렇게 계산된 값이 N의 오일러 피 함수 값이다.