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

## Reply