Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Basics

Prime Factorization

Easy · Basics · Asked at TCS, Infosys, Wipro, Accenture, Cognizant

Print all prime factors of n in non-decreasing order, repeating each one as many times as it divides n. For example 60 = 2 × 2 × 3 × 5.

Input

A single integer n.

Output

The prime factors, space-separated.

Constraints

Divide out each factor d while d·d ≤ n; whatever is left above 1 is itself prime.

Example 1

Input

60

Output

2 2 3 5

Example 2

Input

97

Output

97

Hints

  1. Try dividing by 2, 3, 4, … — composite divisors never succeed because their prime parts were already divided out.
  2. Stop when d·d > n. If n is still above 1, it is a prime factor.

Approach

Trial division: for d = 2, 3, … while d·d ≤ n, divide n by d as many times as possible and record d each time. Any remaining n > 1 has no factor ≤ its square root, so it is prime — record it too. The factors come out in increasing order automatically.

Complexity: O(√n) time · O(log n) space

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long n;
    cin >> n;
    vector<long long> f;
    for (long long d = 2; d * d <= n; d++)
        while (n % d == 0) {
            f.push_back(d);
            n /= d;
        }
    if (n > 1) f.push_back(n);
    for (size_t i = 0; i < f.size(); i++) cout << f[i] << (i + 1 < f.size() ? " " : "\n");
    return 0;
}

Python solution

n = int(input())
f = []
d = 2
while d * d <= n:
    while n % d == 0:
        f.append(d)
        n //= d
    d += 1
if n > 1:
    f.append(n)
print(*f)

Java solution

import java.util.*;

public class Main {
    public static void main(String[] args) {
        long n = new Scanner(System.in).nextLong();
        StringBuilder sb = new StringBuilder();
        for (long d = 2; d * d <= n; d++)
            while (n % d == 0) {
                sb.append(d).append(' ');
                n /= d;
            }
        if (n > 1) sb.append(n);
        System.out.println(sb.toString().trim());
    }
}

Solve Prime Factorization online · All practice problems