Mobius Function

mobius.py

import math

def mobius(n):
    ctr = 0
    k = int(math.sqrt(n)) + 1
    primes = [True] * k
    primes[0], primes[1] = False, False
    for i in range(k):
        if primes[i]:
            j = 2
            while i * j < k:
                primes[i * j] = False
                j += 1
    for i in range(k):
        if primes[i]:
            curr = 0
            while n % i == 0:
                n = n // i
                curr += 1
            if curr > 1:
                return 0
            elif curr == 1:
                ctr += 1
    return 1 - 2 * ctr % 2