# 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: EASY
Tags: Ad-hoc

Starter code:
def mobius(n):
	

Solutions:
def mobius(n):
	(sP, p) = (set(), 2)
	while n > 1 and p <= n ** 0.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 ** 0.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 ** 0.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 ** 0.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):
		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