Informatica Online Judge

  소인수분해 [0681 / 02A9]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 503   Total Tried : 524


The Champion of this Problem (C++) : gs16109 - 0ms / 84byte
My Best Submission (C++) : N/A

[]

Background

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

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

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

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

Input

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

Output

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

IO Example

입력1
7

출력1
7

입력2
72

출력2
2 2 2 3 3

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]