## 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

Advertisements

## Reply