Given a number N, find the least prime factors for all numbers from 1 to N.  The least prime factor of an integer X is the smallest prime number that divides it.
Note : 
1 needs to be printed for 1.
You need to return an array/vector/list of size N+1 and need to use 1-based indexing to store the answer for each number.
Example 1:
Input: N = 6
Output: [0, 1, 2, 3, 2, 5, 2] 
Explanation: least prime factor of 1 = 1,
least prime factor of 2 = 2,
least prime factor of 3 = 3,
least prime factor of 4 = 2,
least prime factor of 5 = 5,
least prime factor of 6 = 2.
So answer is[1, 2, 3, 2, 5, 2]. 
Example 2:
Input: N = 4
Output: [0, 1, 2, 3, 2]
Explanation: least prime factor of 1 = 1,
least prime factor of 2 = 2,
least prime factor of 3 = 3,
least prime factor of 4 = 2.
So answer is[1, 2, 3, 2]. 
Your Task:  
You don't need to read input or print anything. Complete the function leastPrimeFactor() which takes N as input parameter and returns a list of integers containing all the least prime factors of each number from 1 to N.
Expected Time Complexity: O(NlogN)
Expected Auxiliary Space: O(N)
Constraints:
2<= n <=10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: Number theory

Mathematics

Starter code: #User function Template for python3

class Solution:

    def leastPrimeFactor (self, n):

        # code here 

Solutions:
class Solution:

	def leastPrimeFactor(self, n):
		lpf = [i for i in range(n + 1)]
		lpf[1] = 1
		for i in range(2, n + 1):
			if i == lpf[i]:
				j = i
				while j < n + 1:
					if lpf[j] == j:
						lpf[j] = i
					j = j + i
		lpf.append(0)
		return lpf[1:]


class Solution:

	def leastPrimeFactor(self, N):
		res = [1 for i in range(N + 2)]
		for i in range(2, N + 2):
			if res[i] == 1:
				res[i] = i
				for j in range(i * i, N + 2, i):
					if res[j] == 1:
						res[j] = i
		return res[1:]


class Solution:

	def isprime(self, N):
		if N == 1:
			return False
		for i in range(2, int(N ** 0.5) + 1, 1):
			if N % i == 0:
				return False
		return True

	def leastPrimeFactor(self, n):
		l = [1]
		for i in range(2, n + 2):
			for j in range(2, i + 1):
				if self.isprime(j) and i % j == 0:
					l.append(j)
					break
		return l


class Solution:

	def leastPrimeFactor(self, n):
		ans = [0] * (n + 2)
		ans[1] = 1
		for i in range(2, n + 2):
			if ans[i] == 0:
				ans[i] = i
				for j in range(i * i, n + 1, i):
					if ans[j] == 0:
						ans[j] = i
		return ans[1:]


import math

def fun(n):
	if n <= 0:
		return False
	for i in range(2, int(math.sqrt(n)) + 1):
		if n % i == 0:
			return False
	return True

class Solution:

	def leastPrimeFactor(self, n):
		d = []
		for i in range(1, n + 1):
			if fun(i) or i == 1:
				d.append(i)
			else:
				for j in range(2, i // 2 + 1):
					if i % j == 0:
						d.append(j)
						break
		if fun(n):
			d.append(n)
		else:
			for i in range(2, n // 2 + 1):
				if n % i == 0:
					d.append(i)
					break
		return d


import math

class Solution:

	def __init__(self):
		self.lpf = self.primeFactors()

	def primeFactors(self):
		(n, pl) = (int(1000.0), [])
		for i in range(n + 1):
			pl.append(i)
		lim = int(math.sqrt(n)) + 1
		for i in range(2, lim):
			if pl[i] == i:
				for j in range(i * i, n + 1, i):
					if pl[j] == j:
						pl[j] = i
		res = [pl[i] for i in range(n + 1)]
		return res

	def leastPrimeFactor(self, n):
		res = []
		for i in range(1, n + 2):
			res.append(self.lpf[i])
		return res


class Solution:
	m = 10 ** 3
	primes = []
	max_prime = m + 1
	sieve = [1] * max_prime
	for i in range(2, max_prime):
		if sieve[i]:
			primes.append(i)
			for j in range(i * i, max_prime, i):
				sieve[j] = 0

	def solve(self, num):
		for i in self.primes:
			if num % i == 0:
				return i

	def leastPrimeFactor(self, n):
		answer = []
		for i in range(1, n + 1):
			if i == 1:
				answer.append(1)
			elif i % 2 == 0:
				answer.append(2)
			else:
				a = self.solve(i)
				answer.append(a)
		answer.append(0)
		return answer


class Solution:

	def leastPrimeFactor(self, n):
		p = [0] * (n + 1)
		for i in range(n + 1):
			digit = i + 1
			if digit == 1:
				p[i] = digit
			elif digit % 2 == 0:
				p[i] = 2
			else:
				for j in range(3, digit + 1):
					if digit % j == 0:
						p[i] = j
						break
		return p


import math

class Solution:

	def checkPrime(N):
		count = 0
		for i in range(1, int(math.sqrt(N)) + 1):
			if N % i == 0:
				if i * i == N:
					count += 1
				else:
					count += 2
		if count == 2:
			return 1
		return 0

	def leastPrimeFactor(self, n):
		result = []
		for i in range(1, n + 2):
			if i == 1:
				result.append(i)
			elif Solution.checkPrime(i):
				result.append(i)
			else:
				for k in range(1, int(math.sqrt(i)) + 1):
					if i % k == 0 and Solution.checkPrime(k):
						result.append(k)
						break
		return result


class Solution:

	def leastPrimeFactor(self, n):
		k = 0
		prime = []
		while k <= n:
			if k + 1 == 1:
				prime.append(1)
			if k + 1 & 1 == 0:
				prime.append(2)
			if k + 1 & 1 != 0:
				p = 2
				while k + 1 > 1:
					if (k + 1) % p == 0:
						prime.append(p)
						break
					p += 1
			k += 1
		return prime


class Solution:

	def leastPrimeFactor(self, n):
		arr = [i for i in range(n + 2)]
		for i in range(2, n + 1):
			if arr[i] != i:
				continue
			for j in range(i, n + 2, i):
				if arr[j] != j:
					continue
				arr[j] = i
		res = []
		for i in range(1, n + 2):
			res.append(arr[i])
		return res


class Solution:

	def leastPrimeFactor(self, n):
		sieve = [True] * (n + 1)
		sieve[0] = sieve[1] = False
		p = [1] * n
		for i in range(2, n + 1):
			if sieve[i]:
				for j in range(i, n + 1, i):
					sieve[j] = False
					if p[j - 1] == 1:
						p[j - 1] = i
		p.append(-1)
		return p


import math

class Solution:

	def leastPrimeFactor(self, n):
		l = [0] * (n + 2)
		l[1] = 1
		for i in range(2, n + 2):
			if l[i] == 0:
				l[i] = i
				for j in range(i * i, n + 2, i):
					if l[j] == 0:
						l[j] = i
		return l[1:]


import math

def prime(n):
	for i in range(2, int(math.sqrt(n)) + 1):
		if n % i == 0:
			return False
	return True

def fact(n):
	l = []
	l1 = []
	for i in range(2, n + 1):
		if n % i == 0:
			if prime(i):
				l.append(i)
	a = min(l)
	return a

class Solution:

	def leastPrimeFactor(self, n):
		l = []
		for i in range(1, n + 2):
			if i == 1:
				l.append(i)
			else:
				a = fact(i)
				l.append(a)
		return l


import math

class Solution:

	def leastPrimeFactor(self, n):
		sieve = [i for i in range(1001)]
		self.populatesieve(sieve)
		res = sieve[1:n + 1]
		res.append(None)
		return res

	def populatesieve(self, sieve):
		for i in range(4, 1001, 2):
			sieve[i] = 2
		for i in range(3, int(math.sqrt(1001)) + 1, 2):
			if sieve[i] == i:
				for j in range(i * i, 1001, i):
					if sieve[j] == j:
						sieve[j] = i


class Solution:

	def leastPrimeFactor(self, n):
		if n == 1:
			return [1, None]
		if n == 2:
			return [1, 2, None]
		if n == 3:
			return [1, 2, 3, None]
		res = [1, 2, 3]
		for i in range(4, n + 1):
			res.append(self.find(i))
		res.append(None)
		return res

	def find(self, n):
		if n % 2 == 0:
			return 2
		if n % 3 == 0:
			return 3
		i = 5
		while i * i <= n:
			if n % i == 0:
				return i
			elif n % (i + 2) == 0:
				return i + 2
			i += 6
		return n


class Solution:

	def leastPrimeFactor(self, n):
		a = [[i, 0] for i in range(2, n + 1)]
		for (x, y) in a:
			if y == 0:
				i = 1
				while x * i <= n:
					if a[x * i - 2][1] == 0:
						a[x * i - 2][1] = x
					i += 1
		p = [1]
		for i in a:
			p.append(i[1])
		p.append('fuck you geeksforgeeks for 1 based indexing')
		return p


class Solution:

	def leastPrimeFactor(self, n):

		def isprime(m):
			for j in range(2, m + 1):
				if m % j == 0:
					return j
			return 1
		K = []
		for i in range(1, n + 2):
			K.append(isprime(i))
		return K


import math

class Solution:

	def leastPrimeFactor(self, n):

		def isprime(x):
			if x < 1:
				return False
			if x == 1:
				return True
			for i in range(2, int(math.sqrt(x)) + 1):
				if x % i == 0:
					return False
			return True
		ans = [1]
		for i in range(2, n + 2):
			for j in range(2, i + 1):
				if i % j == 0 and isprime(j):
					ans.append(j)
					break
		return ans


class Solution:

	def leastPrimeFactor(self, n):
		sieve = [0 for i in range(n + 1)]
		sieve[1] = 1
		i = 2
		while i <= n:
			if sieve[i] == 0:
				sieve[i] = i
				x = i * i
				while x <= n:
					if sieve[x] == 0:
						sieve[x] = i
					x += i
			i += 1
		for i in range(n):
			sieve[i] = sieve[i + 1]
		return sieve


class Solution:

	def leastPrimeFactor(self, n):
		k = []
		k.append(1)
		for i in range(2, n + 2):
			p = 2
			while i > 1:
				if i % p == 0:
					k.append(p)
					break
				else:
					p = p + 1
		return k


import math

class Solution:

	def prime(self, n):
		if n == 1:
			return 1
		if n == 2:
			return 1
		for i in range(2, int(math.sqrt(n)) + 1):
			if n % i == 0:
				return 0
		return 1

	def leastPrimeFactor(self, n):
		num = [1]
		for i in range(2, n + 2):
			for j in range(2, i + 1):
				if i % j == 0 and self.prime(j):
					num.append(j)
					break
		return num


from math import sqrt

class Solution:

	def leastPrimeFactor(self, n):
		k = 0
		prime = []
		while k <= n:
			if k + 1 == 1:
				prime.append(1)
			if k + 1 & 1 == 0:
				prime.append(2)
			if k + 1 & 1 != 0:
				p = 2
				while k + 1 > 1:
					if (k + 1) % p == 0:
						prime.append(p)
						break
					p += 1
			k += 1
		return prime


class Solution:

	def leastPrimeFactor(self, n):

		def is_prime(x):
			if x == 0 or x == 1:
				return False
			if x == 2:
				return True
			for i in range(2, int(x ** 0.5) + 1):
				if x % i == 0:
					return False
			return True
		ans = [1]
		for i in range(2, n + 2):
			if i % 2 == 0:
				ans.append(2)
			else:
				for j in range(3, i + 1):
					if is_prime(j) and i % j == 0:
						ans.append(j)
						break
		return ans


class Solution:

	def leastPrimeFactor(self, n):

		def p(n):
			if n == 0 or n == 1:
				return False
			s = int(n ** 0.5)
			for i in range(2, s + 1):
				if n % i == 0:
					return False
			return True
		e = []
		for i in range(1, n + 2):
			for j in range(1, i + 1):
				if i % j == 0:
					if p(j):
						a = j
						break
			e.append(j)
		return e


import math

class Solution:

	def leastPrimeFactor(self, n):
		prime = [True] * (n + 1)
		for i in range(2, n + 1):
			if prime[i]:
				for j in range(i * i, n + 1, i):
					prime[j] = False
		res = []
		for i in range(1, n + 1):
			if prime[i]:
				res.append(i)
			elif i % 2 == 0:
				res.append(2)
			elif i % 3 == 0:
				res.append(3)
			else:
				for j in range(5, int(math.sqrt(i)) + 1, 6):
					if i % j == 0:
						res.append(j)
						break
					if i % (j + 2) == 0:
						res.append(j + 2)
						break
		res.append(0)
		return res


class Solution:

	def leastPrimeFactor(self, n):
		primes = [0] * (n + 1)
		primes[1] = 1
		i = 2
		while i <= n:
			if primes[i] == 0:
				primes[i] = i
				for j in range(i * 2, n + 1, i):
					if primes[j] == 0:
						primes[j] = i
			i += 1
		lst = [primes[i] for i in range(1, len(primes))]
		lst.append(0)
		return lst


class Solution:

	def leastPrimeFactor(self, n):
		x = [0] * (n + 1)
		x[1] = 1
		for i in range(2, n + 1):
			if x[i] == 0:
				x[i] = i
				for j in range(i * i, n + 1, i):
					if x[j] == 0:
						x[j] = i
		x.pop(0)
		x.append(0)
		return x


class Solution:

	def leastPrimeFactor(self, n):
		spf = [0] * (n + 2)
		for i in range(n + 2):
			spf[i] = i
		for i in range(2, int(n ** 0.5) + 1):
			if spf[i] == i:
				for j in range(i * i, n + 2, i):
					if spf[j] == j:
						spf[j] = i
		return spf[1:]


class Solution:

	def leastPrimeFactor(self, n):
		h = 0
		l = []
		while h <= n:
			if h + 1 == 1:
				l.append(1)
			if h + 1 & 1 == 0:
				l.append(2)
			if h + 1 & 1 != 0:
				p = 2
				while h + 1 > 1:
					if (h + 1) % p == 0:
						l.append(p)
						break
					p += 1
			h += 1
		return l


class Solution:

	def leastPrimeFactor(self, n):
		l1 = [0] * (n + 1)
		l1[1] = 1
		for i in range(2, n + 1):
			if l1[i] == 0:
				l1[i] = i
				for j in range(i * 2, n + 1, i):
					if l1[j] == 0:
						l1[j] = i
		l2 = l1[1:]
		l2.append(0)
		return l2


class Solution:

	def leastPrimeFactor(self, n):
		l = []
		for i in range(1, n + 2):
			if i == 1:
				l.append(1)
			elif i % 2 == 0:
				l.append(2)
			else:
				for j in range(3, n + 2):
					if i % j == 0:
						l.append(j)
						break
		return l


class Solution:

	def leastPrimeFactor(self, n):
		ans = []
		for i in range(1, n + 2):
			if self.prime(i):
				ans.append(i)
			else:
				ans.append(self.factor(i))
		return ans

	def prime(self, n):
		for i in range(2, n):
			if n % i == 0:
				return False
		return True

	def factor(self, n):
		ans = []
		for i in range(2, n):
			if n % i == 0:
				ans.append(i)
		return ans[0]


class Solution:

	def leastPrimeFactor(self, n):
		list = []
		for i in range(1, n + 2):
			if i == 1:
				prime = 1
			elif i % 2 == 0:
				prime = 2
			else:
				for j in range(2, i + 1):
					if i % j == 0:
						prime = j
						break
			list.append(prime)
		return list


import math

class Solution:

	def leastPrimeFactor(self, n):
		prime = [-1 for i in range(n + 1)]
		prime[1] = 1
		prime[0] = 0

		def isPrime(x):
			for i in range(2, int(math.sqrt(x) + 1)):
				if x % i == 0:
					return 0
			return 1
		for i in range(2, n + 1):
			if isPrime(i) == 1:
				for j in range(i, n + 1):
					if prime[j] == -1:
						if j % i == 0:
							prime[j] = i
		prime.pop(0)
		prime.append(-1)
		return prime


class Solution:

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


class Solution:

	def leastPrimeFactor(self, n):
		arr = []
		for i in range(n + 2):
			arr.append(0)
		arr[1] = 1
		for i in range(2, len(arr)):
			for j in range(i, len(arr)):
				if j % i == 0:
					if arr[j] == 0:
						arr[j] = i
					else:
						continue
		return arr[1:]


import math

class Solution:

	def leastPrimeFactor(self, n):
		l = []
		for i in range(1, n + 2):
			f = 1
			if i == 1:
				l.append(i)
			elif i % 2 == 0:
				l.append(2)
			else:
				for j in range(2, int(math.sqrt(i)) + 1):
					if i % j == 0:
						l.append(j)
						break
				else:
					l.append(i)
		return l


class Solution:

	def leastPrimeFactor(self, n):
		lista = []
		lista.append(1)
		for i in range(2, n + 2):
			if i % 2 == 0:
				lista.append(2)
			else:
				for j in range(2, i + 1):
					if i % j == 0:
						lista.append(j)
						break
		return lista


def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	prime[0] = prime[1] = False
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return prime
primes = []
prime = SieveOfEratosthenes(10 ** 4 + 1)
for i in range(10 ** 4 + 1):
	if prime[i]:
		primes.append(i)

class Solution:

	def leastPrimeFactor(self, n):
		ans = []
		for i in range(1, n + 2):
			if i == 1:
				ans.append(1)
				continue
			for p in primes:
				if i % p == 0:
					ans.append(p)
					break
		return ans
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		n = int(input())
		ob = Solution()
		ans = ob.leastPrimeFactor(n)
		for i in range(len(ans) - 1):
			print(ans[i], end=' ')
		print()


class Solution:

	def findFactor(self, n):
		if n == 1:
			return 1
		for i in range(3, int(n ** 0.5) + 1, 2):
			if n % i == 0:
				return i
		if n > 2:
			return n

	def leastPrimeFactor(self, n):
		if n == 0:
			return [0]
		ans = []
		for i in range(1, n + 2):
			if i % 2 == 0:
				ans.append(2)
			else:
				ans.append(self.findFactor(i))
		return ans
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		n = int(input())
		ob = Solution()
		ans = ob.leastPrimeFactor(n)
		for i in range(len(ans) - 1):
			print(ans[i], end=' ')
		print()


class Solution:

	def leastPrimeFactor(self, n):
		Seen = [False for _ in range(n + 1)]
		res = [i for i in range(n + 1)]
		for i in range(2, n + 1):
			if Seen[i]:
				continue
			if i * i > n:
				break
			for j in range(i * i, n + 1, i):
				res[j] = min(res[j], i)
				Seen[j] = True
		return res[1:] + [0]
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		n = int(input())
		ob = Solution()
		ans = ob.leastPrimeFactor(n)
		for i in range(len(ans) - 1):
			print(ans[i], end=' ')
		print()


import math

class Solution:

	def leastPrimeFactor(self, n):
		ans = []
		ans.append(1)
		for i in range(2, n + 2):
			ans.append(self.leastPrime(i))
		return ans

	def leastPrime(self, n):
		for i in range(2, int(math.sqrt(n)) + 1):
			if n % i == 0:
				if self.isPrime(i):
					return i
		return n

	def isPrime(self, n):
		if n == 1:
			return 0
		if n == 2 or n == 3 or n == 5 or (n == 7):
			return 1
		for i in range(2, int(math.sqrt(n)) + 1):
			if n % i == 0:
				return 0
		return 1


class Solution:

	def leastPrimeFactor(self, n):
		k = 0
		prime = []
		while k <= n:
			if k + 1 == 1:
				prime.append(1)
			if k + 1 & 1 == 0:
				prime.append(2)
			if k + 1 & 1 != 0:
				p = 2
				while k + 1 > 1:
					if (k + 1) % p == 0:
						prime.append(p)
						break
					p += 1
			k += 1
		return prime
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		n = int(input())
		ob = Solution()
		ans = ob.leastPrimeFactor(n)
		for i in range(len(ans) - 1):
			print(ans[i], end=' ')
		print()