Problem: Prime Factors and their Powers

*Difficulty: Easy

Given a number N, print all its unique prime factors and their powers in N.

N = 100
Factor Power
  2      2
  5      2

N = 35
Factor  Power
  5      1
  7      1

Input:
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 all prime factors and their powers separated by spaces.  The output should be printed in increasing order of prime factors.

Constraints:
1 ≤ T ≤ 200
2 ≤ N ≤ 10000

Example:
Input:
2
100
35

Output:
2 2 5 2
5 1 7 1
Implementation: Python 2.7, using Sieve Eratosthenes to generate a list of primes.

from math import sqrt
def sieve_eratosthenes(n):
    sieve = [True]*n
    sieve[0] = sieve[1] = False 
    for i in xrange(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(10000)

def prime_factors_and_powers(n):
    count, factors_powers = 0, {}
    while n > 2:
        power = 0
        while n % primes[count] == 0:
            power += 1
            n /= primes[count]
        if power > 0:
            factors_powers[primes[count]] = power
        count += 1
    return factors_powers

if __name__ == '__main__':
    t = input()
    for _ in xrange(t):
        n = input()
        factors_and_powers = prime_factors_and_powers(n)
        for key in sorted(factors_and_powers):
            print key, factors_and_powers[key], 
        print

Advertisements