e577: 10042 - Smith Numbers
Tags : 質因數分解 質數
Accepted rate : 35人/41人 ( 85% ) [非即時]
評分方式:
Tolerant

最近更新 : 2019-10-30 00:18

Content

Lehigh大學的數學家Albert Wilansky在1982年瀏覽電話簿時,注意到他的岳母H. Smith的電話號碼具有以下特殊性質:
該數字位數的總和等於該數字質因數分解後所有質數的位數的總和。
有了解嗎?比方說:
H. Smith的電話號碼是493-7775。該號碼可以寫成數字4937775。
將4937775質因數分解:4937775 = 3 * 5 * 5 * 65837。
電話號碼的數字位數總和為4 + 9 + 3 + 7 + 7 + 7 + 5 = 42。
質因數分解後所有質數位數總和為3 + 5 + 5 + 6 + 5 + 8 + 3 + 7 = 42。
Wilansky對自己的發現感到非常驚訝,以至於他以岳母的名字命名了這種類型的數字:Smith Number。
由於此性質適用於每個質數,因此Wilansky後來決定,"質數"不值得成為Smith Number,因此他將其排除在外。
之後Wilansky在《兩年制大學數學雜誌》上發表了一篇有關Smith Number的文章,並且能夠呈現一整套不同的Smith Number。
例如:9985是Smith Number,6036也是如此。但是,Wilansky找不到比4937775還要大的Smith Number。
因此,找到比4937775更大的Smith Number是您的任務。

Input

輸入第一行包含一個整數T,代表有幾組測資。
接下來每組測資一行包含一個正整數N (0 < N < 10^9)。

Output

對於每組測資,輸出大於N的最小Smith Number。
Smith Number一定存在。

Sample Input #1
1
4937774
Sample Output #1
4937775
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (100%): 1.0s , <1K
Hint :
Tags:
質因數分解 質數
出處:
UVA [管理者:
ig99lp33lp33 (위즈원)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」