Problem: Least Prime Factor

• Difficulty: Easy

Given a number N, print least prime factors for all numbers from 1 to N.  The least prime factor of an integer N is the smallest prime number that divides it. The least prime factor of all even numbers is 2. A prime number is its own least prime factor (as well as its own greatest prime factor).  Note : 1 needs to be printed for 1.

```Input: N = 6
Output: 1 2 3 2 5 2
```

The first line of input contains an integer T denoting the number of test cases.
The first line of each test case is N.

Output:
Print least prime factors separated by space
Constraints:
1 ≤ T ≤ 200
2 ≤ N ≤ 1000

Example:
Input:
2
6
10

Output:
1 2 3 2 5 2
1 2 3 2 5 2 7 2 3 2

Implementation: Python 2.7

```from math import sqrt
def sieve_eratosthenes(n):
# create first n prime numbers
sieve = [True] * (n+1)
sieve[0] = False
sieve[1] = False
for i in xrange(2, int( sqrt(len(sieve)))):
if sieve[i]:
for j in xrange(i+i, len(sieve), i):
sieve[j] = False
return [i for i in range(len(sieve)) if sieve[i]]

primes = sieve_eratosthenes(1000)

if __name__ == '__main__':
t = input()
for i in xrange(t):
n = input()
for _ in xrange(1,n+1):
if _ == 1:
print 1,
continue
index = 0
while _ % primes[index] != 0:
index += 1
print primes[index],
print
```