# Task
 Mobius function - an important function in number theory. For each given n, it only has 3 values:
```
0  -- if n divisible by square of a prime. Such as: 4, 8, 9
1  -- if n not divisible by any square of a prime 
        and have even number of prime factor. Such as: 6, 10, 21
-1 -- otherwise. Such as: 3, 5, 7, 30```
Your task is to find mobius(`n`)

# Input/Output


 - `[input]` integer `n`


 `2 <= n <= 1e12`


 - `[output]` an integer

Difficulty: introductory

Starter code:

def mobius(n):
	

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

def mobius(n):
    s, p, m = 0, 2, n ** .5
    while p <= m:
        if not n % p:
            s += 1
            n //= p
        if not n % p:
            return 0
        p += 1
    if n > 1:
        s += 1
    return 1 - s % 2 * 2

LIMIT = 10**6
sieve = [True] * (LIMIT//2)
for n in range(3, int(LIMIT**0.5) +1, 2):
    if sieve[n//2]: sieve[n*n//2::n] = [False] * ((LIMIT-n*n-1)//2//n +1)
PRIMES = [2] + [2*i+1 for i in range(1, LIMIT//2) if sieve[i]]
del sieve


def mobius(n):
    factors = []
    for p in PRIMES:
        if p*p > n:
            factors.append(n)
            break
        while n % p == 0:
            if p in factors:
                return 0
            factors.append(p)
            n //= p
        if n == 1:
            break
    
    return -1 if len(factors) % 2 else 1


from collections import Counter

def prime_factors(n):
    factors = Counter()
    d = 2
    while d ** 2 <= n:
        while n % d == 0:
            n //= d
            factors[d] += 1
        d += 1 + (d > 2)
    if n > 1:
        factors[n] += 1
    return factors


def mobius(n):
    factors = prime_factors(n)
    if any(c > 1 for c in factors.values()):
        return 0
    elif sum(factors.values()) % 2 == 0:
        return 1
    return -1

def mobius(n):
  a = 0
  for i in range(2, int(n ** .5) + 1):
    if n % i == 0:
      if isPrime(i):
        if n % (i*i) == 0:
          return 0
        a += 1
      n = n // i
      if isPrime(n):
        a += 1
        break
  if a > 0 and a % 2 == 0:
    return 1
  return -1  

def isPrime(n):
  for i in range(2, int(n ** .5 + 1)):
    if n % i == 0:
      return False
  return True

def prime_factors(n):
    factors = []
    while not n % 2:
        factors.append(2)
        n = n // 2
    while not n % 3:
        factors.append(3)
        n = n // 3
    k = 5
    step = 2
    while k <= n**0.5:
        if not n % k:
            factors.append(k)
            n = n // k
        else:
            k = k + step
            step = 6 - step
    factors.append(n)
    return factors

def mobius(n):
    factors = prime_factors(n)
    l = len(factors)
    if l == len(set(factors)):
        if l % 2:
            return -1
        return 1
    return 0


def mobius(n):
    d, k = 2, 0
    while d * d <= n:
        if n % d == 0:
            n //= d
            if n % d == 0:
                return 0
            k += 1
        d += 1
    if n > 1:
        k += 1
    return 1 - k % 2 * 2

def prime_factors_count(num):
    factors_count = 0
    while num % 2 == 0:
        factors_count += 1
        num /= 2

    i = 3
    max_factor = num**0.5
    while i <= max_factor:
        while num % i == 0:
            factors_count += 1
            num /= i
            max_factor = num**0.5
        i += 2

    if num > 1:
        factors_count += 1
    return factors_count

def find_prime_numbers(max_num):
    if max_num == 0:
        return []

    is_prime = [True] * (max_num+1)
    for i in range(4, max_num, 2):
        is_prime[i] = False
    is_prime[0], is_prime[1] = False, False

    next_prime = 3
    stop_at = max_num**0.5
    while next_prime <= stop_at:
        for i in range(next_prime*next_prime, max_num+1, next_prime):
            is_prime[i] = False
        next_prime += 2

    prime_numbers = []
    for i in range(len(is_prime)):
        if is_prime[i]:
            prime_numbers.append(i)
    return prime_numbers

def mobius(n):
    for i in find_prime_numbers(int(n**0.5)//2 + 10):   # An empirical trick :)
        if n % (i*i) == 0:
            return 0
    if prime_factors_count(n) % 2 == 0:
        return 1
    return -1

from collections import defaultdict
def prime_factor(n):
    r=defaultdict(int)
    while(n%2==0):
        r[2]+=1
        n//=2
    x=3
    while(n>1 and x*x<=n):
        while(n%x==0):
            r[x]+=1
            n//=x
        x+=2
    if n>1:
        r[n]+=1
    return r

def mobius(n):
    fs=prime_factor(n)
    if max(fs.values())>1:
        return 0
    elif len(fs.keys())%2==0:
        return 1
    else:
        return -1