Given a number n, find the total numbers, less than or equal to n which have at-least one common factor with n other than 1.
 
Example 1:
Input: n = 6
Output: 4
Explanation: For n=6, the 4 numbers having 
a common factor between them and 6 
are : 2, 3, 4 & 6
Example 2:
Input: n = 15
Output: 7
Explanation: For N=15, the 7 numbers having a 
common factor between them and 15 
are : 3, 5, 6, 9, 10, 12, 15
 
Your Task:
You don't need to read or print anything. Your task is to complete the function CommonFactor() which takes n as input parameter and returns total numbers. less than or equal to n which have atleast one common factor with n other than 1.
 
Expected Time Complexity: O(nlog(n))
Expected Space Complexity: O(n)
Constraints:
1 <= n <= 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Number theory

Starter code: #User function Template for python3

class Solution:
	def CommonFactor(self, n):
		# Code here

Solutions:
class Solution:

	def CommonFactor(self, n):
		sieve = [True] * (n + 1)
		res = [False] * (n + 1)
		for i in range(2, n + 1):
			if sieve[i]:
				can = n % i == 0
				for j in range(i, n + 1, i):
					sieve[j] = False
					res[j] |= can
		return sum(res)


class Solution:

	def CommonFactor(self, n):
		fact = {}
		temp = n
		i = 2
		while i <= temp:
			while temp % i == 0:
				fact[i] = 0
				temp //= i
			i += 1
		if temp != 1:
			fact[temp] = 1
		arr = fact.keys()
		ans = 0
		for i in range(2, n + 1):
			for num in arr:
				if i % num == 0:
					ans += 1
					break
		return ans


class Solution:

	def CommonFactor(self, num):
		factors = set()
		i = 2
		tmp = num
		while tmp > 1:
			if tmp % i == 0:
				factors.add(i)
				tmp //= i
			else:
				i += 1
		i = 2
		cnt = 0
		while i <= num:
			for a in factors:
				if i % a == 0:
					cnt += 1
					break
			i += 1
		return cnt


class Solution:

	def CommonFactor(self, n):
		if n <= 0:
			return 0
		v = [i for i in range(0, n + 1)]
		for i in range(2, n + 1):
			if v[i] == i:
				for j in range(i, n + 1, i):
					v[j] *= i - 1
					v[j] /= i
		return int(n - v[n])


class Solution:

	def CommonFactor(self, m):
		i = 2
		n = m
		res = n
		(num, den) = (1, 1)
		while i * i <= n:
			c = 0
			while n % i == 0:
				n //= i
				c += 1
			if c > 0:
				num *= i - 1
				den *= i
			i += 1
		if n > 1:
			num *= n - 1
			den *= n
		return m - m * num // den
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		n = int(input())
		ob = Solution()
		ans = ob.CommonFactor(n)
		print(ans)


import math

class Solution:

	def CommonFactor(self, N):
		count = 0
		for i in range(1, N + 1):
			if math.gcd(i, N) != 1:
				count += 1
		return count


import math

class Solution:

	def CommonFactor(self, n):

		def euler(n):
			count = n
			for i in range(2, int(math.sqrt(n)) + 1):
				if n % i == 0:
					count = count - count / i
					while n % i == 0:
						n = n / i
			if n > 1:
				count = count - count / n
			return count
		return n - int(euler(n))


import math

class Solution:

	def CommonFactor(self, n):
		c = 0
		for i in range(2, n + 1):
			if n % i == 0:
				c += 1
			elif math.gcd(i, n) != 1:
				c += 1
		return c


import math

class Solution:

	def CommonFactor(self, n):
		c = 0
		f = []
		for i in range(2, n + 1):
			if n % i == 0:
				f.append(i)
				c += 1
				continue
			for j in f:
				if i % j == 0:
					c += 1
					break
		return c


class Solution:

	def CommonFactor(self, n):

		def gcd(a, b):
			while b != 0:
				(a, b) = (b, a % b)
			return a
		f = []
		for i in range(2, n + 1):
			if n % i == 0 or gcd(i, n) != 1:
				f.append(i)
		return len(f)


class Solution:

	def CommonFactor(self, n):
		ans = 0
		b = [j for j in range(2, n // 2 + 1) if n % j == 0]
		b.append(n)
		for i in range(2, n + 1):
			for j in b:
				if i % j == 0:
					ans += 1
					break
		return ans


class Solution:

	def CommonFactor(self, n):
		a = 1
		c = [True] * (n + 1)
		while a <= n:
			a = a + 1
			if n % a == 0:
				for i in range(a, n + 1, a):
					c[i] = False
		d = 0
		for i in range(2, len(c)):
			if c[i] == False:
				d = d + 1
		return d


class Solution:

	def CommonFactor(self, n):

		def gcd(a, b):
			if a == 0:
				return b
			return gcd(b % a, a)
		ans = []
		for i in range(1, n + 1):
			if gcd(i, n) != 1:
				ans.append(i)
		return len(ans)


class Solution:

	def CommonFactor(self, n):
		a = n
		k = n
		for i in range(2, int(n ** 0.5) + 1):
			if n % i == 0:
				while n % i == 0:
					n = n // i
				a *= 1 - 1 / i
		if n > 1:
			a *= 1 - 1 / n
		return k - int(a)


class Solution:

	def CommonFactor(self, n):
		a = 0
		mark = [True] * (1 + n)
		mark[0] = mark[1] = False
		for i in range(2, n + 1):
			if mark[i] and n % i == 0:
				for j in range(i, n + 1, i):
					if mark[j]:
						a += 1
					mark[j] = False
		return a


def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

class Solution:

	def CommonFactor(self, n):
		ctr = 0
		for i in range(2, n + 1):
			if gcd(i, n) != 1:
				ctr += 1
		return ctr


class Solution:

	def CommonFactor(self, n):
		if n == 1:
			return 0
		result = N = n * 1
		i = 2
		while i * i <= n:
			if n % i == 0:
				while n % i == 0:
					n //= i
				result = result * (i - 1) // i
			i += 1
		if n == N:
			return 1
		if n > 1:
			result = result * (n - 1) // n
		return N - result


import math

class Solution:

	def CommonFactor(self, N):
		cont = 0
		for i in range(2, n + 1):
			if math.gcd(i, n) != 1:
				cont += 1
		return cont


class Solution:

	def CommonFactor(self, N):
		prime = [True for i in range(N + 1)]
		l = []
		p = 2
		while p * p < N + 1:
			if prime[p] == True:
				for i in range(p * p, N + 1, p):
					prime[i] = False
			p += 1
		for i in range(2, N + 1):
			if prime[i] == True:
				l.append(i)
		ans = []
		for i in l:
			if N % i == 0:
				a = i
				while a <= N:
					ans.append(a)
					a += i
		return len(set(ans))


import math

class Solution:

	def CommonFactor(self, n):
		if n == 1:
			return 0
		count = 0
		l = []
		for i in range(2, int(math.sqrt(n)) + 1, 1):
			if n % i == 0:
				if i != math.sqrt(n):
					l.append(int(n / i))
				l.append(i)
		l2 = []
		for i in l:
			for j in range(i, n + 1, i):
				l2.append(j)
		l1 = list(set(l2))
		count = len(l1)
		if count:
			return count
		return 1


import math

class Solution:

	def gcd(self, a, b):
		if a == 0:
			return b
		return self.gcd(b % a, a)

	def CommonFactor(self, n):
		ans = 0
		for i in range(2, n + 1):
			if math.gcd(i, n) != 1:
				ans += 1
		return ans


from math import *

class Solution:

	def CommonFactor(self, n):
		count = 0
		for e in range(1, n + 1):
			if gcd(e, n) != 1:
				count += 1
		return count