E D R , A S I H C RSS

Smith Numbers

원문보기
----
인기도:B(A,B,C), 성공률:보통(낮음,보통,높음), 레벨:1(1~4)

About SmithNumbers

1982년, 앨버트 윌란스키(Albert Wilansky)라는 수학자는 그가 가지고 있던 주소록을 훑어보다가 그의 처제인 H. 스미스(H. smith)의 전화번호에 특이한 속성이 있다는 것을 발견했다. 그 수의 각 자리 숫자 합은 그 수의 소인수 각 자리 숫자의 합과 같았다. 잘 이해가 안 된다면 실제 숫자를 예로 들어서 생각해보자. 스미스의 전화번호는 493-7775였다. 이 수는 다음과 같이 소인수분해할 수 있다.

4937775 = 3 x 5 x 5 x 65837

전화번호의 각 자리 숫자의 합은 4+9+3+7+7+7+5=42이고 소인수의 각 자리 숫자의 합은 3+5+5+6+5+8+3+7=42이므로 둘 다 42로 같은 값을 가진다. 윌란스키는 이런 유형의 수에 처제의 이름을 딴, 스미스 수라는 이름을 붙였다.

모든 소수는 이런 속성을 가지기 때문에 소수는 스미스 수에서 제외되었다. 다른 스미스 수로는 6,036과 9,985 등이 있다.

그런데 윌란스키는 그의 처제의 전화번호보다 큰 스미스 수를 찾지 못했다. 윌란스키를 도와서 그 전화번호보다 큰 스미스 수를 찾을 수 있을까?

Input

첫번째 줄에는 테스트 케이스의 개수가 입력된다. 각 테스트 케이스마다 한 줄씩 입력되며, 그 줄에는 10^9보다 작은 양의 정수가 들어있다.

Output

입력된 각각의 값 n에 대해, n보다 큰 가장 작은 스미스 수를 계산해서 그 정수를 출력한다. 한 줄에 하나씩의 결과를 출력한다. 그러한 정수가 반드시 존재한다고 가정해도 된다.

Sample Input

~cpp 
1
4937774

Sample Output

~cpp 
4937775

풀이

작성자 사용언어 개발시간 코드
문보창 C++ 60min SmithNumbers/문보창
도현 C 3h 20m SmithNumbers/이도현
신재동 C++ 47m SmithNumbers/신재동
상협 C++ 43min SmithNumbers/남상협
조현태 C . SmithNumbers/조현태

쓰레드

Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2009-05-27 07:09:19
Processing time 0.1012 sec