Given n you have to find sum of count of divisors from1 to n.
 
Example 1:
Input: n = 2
Output: 3
Explanation: No. of Divisors of 1 = 1,
No of Divisors of 2 = 2(1, 2).
Example 2:
Input: n = 4
Output: 8
Explanation: No. of divisors of 1 = 1
No. of divisors of 2 = 2(1, 2)
No. of divisors of 3 = 2(1, 3)
No. of divisors of 4 = 3(1, 2, 4).
 
Your Task:
You don't need to read or print anything, Your task is to complete the function DivCountSum() which takes n as input parameter and returns the sum of count of divisors from 1 to n.
 
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 DivCountSum(self, n):
		# Code here

Solutions:
class Solution:

	def DivCountSum(self, n):
		c = 0
		for i in range(1, n + 1):
			c += n // i
		return c


class Solution:

	def DivCountSum(self, n):
		sieve = [1] * (n + 1)
		for i in range(2, n + 1):
			if sieve[i] == 1:
				cnt = 1
				while i ** cnt <= n:
					temp = i ** cnt
					mul = 1
					while temp * mul <= n:
						if mul % i == 0:
							pass
						else:
							sieve[temp * mul] *= cnt + 1
						mul += 1
					cnt += 1
		return 1 + sum((sieve[x] for x in range(2, n + 1)))


class Solution:

	def DivCountSum(self, n):
		sum = 0
		for i in range(1, n + 1):
			sum = sum + n // i
		return int(sum)


def countDivisors(n):
	res = n
	for i in range(2, n + 1):
		res += n // i
	return res

class Solution:

	def DivCountSum(self, n):
		return countDivisors(n)


class Solution:

	def DivCountSum(self, n):
		arr = [0] * (n + 1)
		for i in range(1, n + 1):
			for j in range(i, n + 1, i):
				arr[j] += 1
		return sum(arr)


class Solution:

	def DivCountSum(self, n):
		divCnt = [2] * (n + 1)
		divCnt[0] = 0
		divCnt[1] = 1
		for i in range(2, n):
			for j in range(2 * i, n + 1, i):
				divCnt[j] += 1
		sum = 0
		for i in range(len(divCnt)):
			sum += divCnt[i]
		return sum


class Solution:

	def DivCountSum(self, n):
		x = 0
		for i in range(1, n + 1):
			x += n // i
		return x
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		n = int(input())
		ob = Solution()
		ans = ob.DivCountSum(n)
		print(ans)