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