Prime Factorization

View as PDF
Submit solution
Points: 5
Time limit: 1.0s
Memory limit: 128M
Author:
Phoenix1369
Problem type

Oh no! Phoenix1369 is taking ICS this semester and once again, he has left his homework to the last minute. Luckily, it only consisted of one question:

Given a list of natural numbers, output the prime factorization of each number.

Unfortunately, he was too busy typing up this problem statement to do it.

Would you write a program that does his homework for him? As compensation, he will gladly reward you with five points.

Input Specification

The input begins with an integer N, where 1≤N≤1000, indicating the number of lines to follow.
The next N lines will each contain a test case in the form of a single natural number M, where 2≤M≤107.

Output Specification

For each integer M, your program should output the prime factorization of M on a single line, separated with single spaces and sorted in non-decreasing order.

Sample Input

Copy
5
3
13
42
666
1369

Sample Output

Copy
3
13
2 3 7
2 3 3 37
37 37

Comments


  • 2
    Ehsian  commented on Jan. 20, 2021, 5:17 p.m. ← edited

    Tips to avoid TLE in java?

    Edit: Figured it out


    • 1
      billsboard  commented on Jan. 20, 2021, 5:19 p.m.

      BigInteger is slow. Don't use it, as it's not required for this problem.


      • 0
        31501357  commented on Jan. 21, 2021, 2:34 a.m.

        You don't even need longs to solve it.