RSA 암호화 알고리즘에서는 매우 큰 두 개의 소수(prime number)를 곱한 값을 키 N으로 사용한다. 이 알고리즘이 해킹으로부터 안전한 이유는 N을 효율적으로 소인수분해하는 알고리즘이 지금까지 발견되지 않았기 때문이다.

소 인수분해는 합성수를 소수의 곱으로 나타내는 방법을 말한다. 산술의 기본 정리에 의하면 1보다 큰 모든 양의 정수는 소수들의 곱으로 표현하는 방법이 (곱의 순서를 바꾸는 것을 제외하면) 유일하게 존재한다. 다음은 소인수분해의 예이다.

35 = 5 × 7
72 = 2 × 2 × 2 × 3 × 3
99,380 = 2 × 2 × 5 × 4,969

하나의 양의 정수가 주어졌을 때, 이 수를 소인수분해 하는 프로그램을 작성하시오. (주어진 수가 소수인 경우에는 그 수를 출력한다.)

1. 하나의 정수 n이 입력된다. (2≤n≤100,000)

1. n을 소인수분해 한 결과를 한 줄에 출력한다.
2. 소수들을 크기가 작은 수부터 큰 수의 순으로 출력한다.
3. 각 소수들은 하나의 공백으로 분리한다.
4. 곱하기 기호는 출력하지 아니한다.