POJ 1142 Smith Numbersの1本の簡単な数学の問題
14364 ワード
分類:数論
作成者:
ACShiryu
時間:2011-8-3
原題:
http://poj.org/problem?id=1142
Smith Numbers
Time Limit: 1000MS
Memory Limit: 10000K
Total Submissions: 8853
Accepted: 3105
Description
While skimming his phone directory in 1982, Albert Wilansky, a mathematician of Lehigh University,noticed that the telephone number of his brother-in-law H. Smith had the following peculiar property: The sum of the digits of that number was equal to the sum of the digits of the prime factors of that number. Got it? Smith's telephone number was 493-7775. This number can be written as the product of its prime factors in the following way:
4937775= 3*5*5*65837
The sum of all digits of the telephone number is 4+9+3+7+7+7+5= 42,and the sum of the digits of its prime factors is equally 3+5+5+6+5+8+3+7=42. Wilansky was so amazed by his discovery that he named this kind of numbers after his brother-in-law: Smith numbers.
As this observation is also true for every prime number, Wilansky decided later that a (simple and unsophisticated) prime number is not worth being a Smith number, so he excluded them from the definition.
Wilansky published an article about Smith numbers in the Two Year College Mathematics Journal and was able to present a whole collection of different Smith numbers: For example, 9985 is a Smith number and so is 6036. However,Wilansky was not able to find a Smith number that was larger than the telephone number of his brother-in-law. It is your task to find Smith numbers that are larger than 4937775!
Input
The input file consists of a sequence of positive integers, one integer per line. Each integer will have at most 8 digits. The input is terminated by a line containing the number 0.
Output
For every number n > 0 in the input, you are to compute the smallest Smith number which is larger than n,and print it on a line by itself. You can assume that such a number exists.
Sample Input
Sample Output
参照コード:
作成者:
ACShiryu
時間:2011-8-3
原題:
http://poj.org/problem?id=1142
Smith Numbers
Time Limit: 1000MS
Memory Limit: 10000K
Total Submissions: 8853
Accepted: 3105
Description
While skimming his phone directory in 1982, Albert Wilansky, a mathematician of Lehigh University,noticed that the telephone number of his brother-in-law H. Smith had the following peculiar property: The sum of the digits of that number was equal to the sum of the digits of the prime factors of that number. Got it? Smith's telephone number was 493-7775. This number can be written as the product of its prime factors in the following way:
4937775= 3*5*5*65837
The sum of all digits of the telephone number is 4+9+3+7+7+7+5= 42,and the sum of the digits of its prime factors is equally 3+5+5+6+5+8+3+7=42. Wilansky was so amazed by his discovery that he named this kind of numbers after his brother-in-law: Smith numbers.
As this observation is also true for every prime number, Wilansky decided later that a (simple and unsophisticated) prime number is not worth being a Smith number, so he excluded them from the definition.
Wilansky published an article about Smith numbers in the Two Year College Mathematics Journal and was able to present a whole collection of different Smith numbers: For example, 9985 is a Smith number and so is 6036. However,Wilansky was not able to find a Smith number that was larger than the telephone number of his brother-in-law. It is your task to find Smith numbers that are larger than 4937775!
Input
The input file consists of a sequence of positive integers, one integer per line. Each integer will have at most 8 digits. The input is terminated by a line containing the number 0.
Output
For every number n > 0 in the input, you are to compute the smallest Smith number which is larger than n,and print it on a line by itself. You can assume that such a number exists.
Sample Input
4937774
0Sample Output
4937775 n ， ， Smith Number 4937774， 4937775 4+9+3+7+7+7+5=42 4937775=3*5*5*65837 3+5+5+6+5+8+3+7=42 4937775 。 ， ， ， ， ， ； 1 A ， ， ， ， ， 参照コード:
1 #include<iostream>
2 #include<cstdlib>
3 #include<cstdio>
4 #include<cstring>
5 #include<algorithm>
6 #include<cmath>
7 using namespace std;
8 bool isprime (int k)
9 {//
10 int t = sqrt ( k + 0.5 );
11 for ( int i = 2 ; i <= t ; i ++ )
12 if ( k % i == 0 )
13 return false;
14 return true;
15 }
16 int sum(int k)
17 {//
18 int i , s;
19 s = 0 ;
20 while ( k != 0 )
21 {
22 i = k % 10 ;
23 s += i ;
24 k = k / 10 ;
25 }
26 return s;
27 }
28 int cut (int k )
29 {// ， ， sum， ， ， sum
30 if ( isprime(k) )
31 return sum (k);
32 for ( int i = (int) sqrt (k + 0.5) ; i >1 ; i -- )
33 if ( k % i == 0 )
34 return cut (i) + cut (k / i) ;
35 }
36 int main()
37 {
38 int n;
39 while ( cin >> n , n )
40 {
41 while ( n ++ )
42 {
43 if (!isprime(n)&&sum(n)==cut(n))
44 break;
45 }
46 cout<<n<<endl;
47 }
48 }