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
- 2 ≤ n ≤ 10^12
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
- Try dividing by 2, 3, 4, … — composite divisors never succeed because their prime parts were already divided out.
- 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());
}
}