[python] 뫼비우스 함수

 

👀 뫼비우스 함수

: 정수가 제곱인수가 없는 정수인지 여부에 따라 분류하는 곱셈적 함수.

기호 : μ(n)

출처 : 네이버 수학백과

예) μ(1) = 1, μ(7) = -1, μ(30) = μ(2×3×5) = (-1)^3 = -1

 

✔️ 뫼비우스 함수

 ⭐ 약수 구하기와 소수 판별하기 응용

def mobius(n):
    d = divisors(n)
    for i in d:
        if i**2 in d:
            return 0
    return (-1)**(sum([is_prime(i) for i in d]))

def divisors(n):
    result = set()
    for i in range(2, int(n**0.5)+1):
        if n%i == 0:
            result.add(i)
            result.add(n//i)
    return sorted(result) + [n]

def is_prime(n):
    return n > 1 and all(n % i != 0 for i in range(2, int(n ** 0.5) + 1))

 

⭐ 소인수분해 함수 응용

def mobius(n):
    a, result = 2, set()
    while n>1 and a <= n**0.5:
        while not n%a:
            if a in result: return 0
            result.add(a)
            n //= a
        a += (1 + (a!=2))
    return (-1)**((len(result) + (n!= 1)) % 2)