시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 39 | 31 | 29 | 82.857% |
7로 나누었을 때, 나머지가 1 또는 6인 숫자를 7N+{1,6} 숫자라고 한다. 하지만, 발음하기 어려우므로 이러한 숫자를 월요일-토요일 숫자라고 하자.
월요일-토요일 숫자 a와 b가 있을 때, ax = b를 만족하는 월요일-토요일 숫자 x가 있다면, a를 b의 월요일-토요일 약수라고 한다. 사실, 월요일-토요일 숫자 a가 b의 약수(일반적인 약수)라면, a는 b의 월요일-토요일 약수이다. 또, 역도 성립한다.
월요일-토요일 소수란 1보다 큰 월요일-토요일 숫자가 1과 자기 자신을 제외하고 월요일-토요일 약수가 없는 수이다. 월요일-토요일 숫자가 소수일 때, 이 수는 월요일-토요일 소수이다. 하지만, 그 역은 성립하지 않는다. 예를 들어, 27은 월요일-토요일 소수이지만, 소수는 아니다.
어떤 월요일-토요일 숫자의 월요일-토요일 약수 중에서 월요일-토요일 소수인 것을 월요일-토요일 소인수라고 한다. 예를 들어, 27은 216의 월요일-토요일 소인수이다. (216 = 27 * 8)
1보다 큰 월요일-토요일 솟자는 하나 또는 그 이상의 월요일-토요일 소수의 곱으로 나타낼 수 있다. 이러한 표현은 유일하지 않다. 예를 들어, 216 = 6 * 6 * 6 = 8 * 27이다.
월요일-토요일 숫자가 주어졌을 때, 월요일-토요일 소인수를 모두 구하는 프로그램을 작성하시오.
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 월요일-토요일 수가 주어진다. 이 수는 1보다 크고, 300000보다 작다. 입력의 마지막 줄에는 1이 주어진다.
입력으로 주어진 월요일-토요일 숫자에 대해서, 그 숫자를 출력하고, ":"을 출력한 다음에 월요일-토요일 소인수를 오름차순으로 출력한다. 모든 월요일-토요일 소인수 앞에는 공백을 한 칸 출력해야 한다.
205920 262144 262200 279936 299998 1
205920: 6 8 13 15 20 22 55 99 262144: 8 262200: 6 8 15 20 50 57 69 76 92 190 230 475 575 874 2185 279936: 6 8 27 299998: 299998
ICPC > Regionals > Asia Pacific > Japan > Japan Domestic Contest > 2008 Japan Domestic Contest B번