2013
12-09

# Smith Numbers

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!

The input 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.

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.

4937774
0

4937775

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int getsum (int x) // getsum_all_letter的函数,我觉得是一个不错的函数,
{
int sum = 0;
while (x)
{
sum += x % 10;
x /= 10;
}
return sum;
}

int main ()
{
int N;
while (cin >> N)
{
if (N == 0)
{
break;

}
for (int x = N + 1; ; x++)
{
int key = x;  // 因为你最后还要把这个数字输出来,所以要提前把初始的数字先存起来.
int sum_all_letter = getsum (key); //所求的和;
int sum_prime = 0; //分解质因数的和;
int flag_prime = 0;//标记是x是不是一个素数;
for (int i = 2; i <= sqrt (key * 1.0); i++)
{
while (key % i == 0)
{
flag_prime++;  //这个就是标记:看初始状态的key是不是个素数,如果是素数就得祛除.
sum_prime += getsum (i); //方法很奇特.
key /= i;
}
}
if (key != 1)
{
sum_prime += getsum (key); // 就是排除除到了最后出现了一个prime number,所以加个语句,判断最后的
}								//那个除数是不是素数.
if (sum_all_letter == sum_prime && flag_prime != 0) //这个思想是真的很不错的,
{
cout << x << endl;
break;
}
}
}
return 0;
}
/*

*/

1. 学算法中的数据结构学到一定程度会乐此不疲的，比如其中的2－3树，类似的红黑树，我甚至可以自己写个逻辑文件系统结构来。

2. 约瑟夫也用说这么长……很成熟的一个问题了，分治的方法解起来o(n)就可以了，有兴趣可以看看具体数学的第一章，关于约瑟夫问题推导出了一系列的结论，很漂亮

3. I like your publish. It is great to see you verbalize from the coronary heart and clarity on this essential subject matter can be easily noticed.

4. /*
* =====================================================================================
*
* Filename: 1366.cc
*
* Description:
*
* Version: 1.0
* Created: 2014年01月06日 14时52分14秒
* Revision: none
* Compiler: gcc
*
* Author: Wenxian Ni (Hello World~), [email protected]
* Organization: AMS/ICT
*
* =====================================================================================
*/

#include
#include

using namespace std;

int main()
{
stack st;
int n,i,j;
int test;
int a[100001];
int b[100001];
while(cin>>n)
{
for(i=1;i>a[i];
for(i=1;i>b[i];
//st.clear();
while(!st.empty())
st.pop();
i = 1;
j = 1;

while(in)
break;
}
while(!st.empty()&&st.top()==b[j])
{
st.pop();
j++;
}
}
if(st.empty())
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
return 0;
}