Large Number Prime Factorization

Time limit1sMemory limit128 MB

Summary
Factorize an integer up to 2^62 into primes and print each prime factor on its own line in increasing order.
Level

Medium7 of 10

Topics
Number theory, Math, Implementation
Solved
No attempts yet

Problem

Factorize a given positive integer into its prime factors.

Input

The first line contains a single integer NN to factorize. (1<N<2621 < N < 2^{62})

Output

Print the prime factors of NN in increasing order, one per line. If a prime factor appears more than once, print it that many times.

Examples3

  1. Example 1

    Input
    18991325453139
    Expected output
    3
3
13
179
271
1381
2423

  2. Example 2

    Input
    2
    Expected output
    2

  3. Example 3

    Input
    8
    Expected output
    2
2
2