## Monday, April 4, 2011

### UVa_10042_Smith_Numbers.cpp

uva10042, poj1142,

# Problem D: Smith Numbers

## Background

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:

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 type 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 and he excluded them from the definition.

## Problem

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 give a Smith number which was larger than the telephone number of his brother-in-law. It is your task to find Smith numbers which are larger than 4937775.

## Input

The input consists of several test cases, the number of which you are given in the first line of the input. Each test case consists of one line containing a single positive integer smaller than 109.

## Output

For every input value n, you are to compute the smallest Smith number which is larger than n and print each number on a single line. You can assume that such a number exists.

## Sample Input

1
4937774

## Sample Output

4937775

Miguel Revilla
2000-11-19

## Solution:

1st, The size of prime table is pretty important.
2nd, The smith number should not be a prime number. Plus, checking this number should be individual. There will be too much work if checking each number when creating the prime table.
3rd,

## Source Code:

//Mon Apr  4 16:35:28 CDT 2011
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define max_primes    31623 //That's the possible biggest prime number.

using namespace std;

bool primes[max_primes];

void gen_primes()
{
primes[0] = primes[1] = false;
for (int i = 2; i < max_primes; ++i)
primes[i] = true;
for (int i = 2; i < max_primes; ++i)
{
if (primes[i])
for (int j = 2; i * j < max_primes; ++j)
primes[i * j] = false;
}
}

int sum(int n)
{
int ret = 0;
while (n > 0)
{
ret += n % 10;
n /= 10;
}
return ret;
}

bool isPrime(int n)
{
if (n == 2) return true;
if (n % 2 == 0) return false;
for (int i = 3; i <= sqrt(1.0 * n); i += 2)
if (n % i == 0)
return false;
return true;
}

bool check(int n)
{
int s = 0;
int record = sum(n);
while (n > 1 && n % 2 == 0)
{
s += sum(2);
n /= 2;
}
//cout << "break one" << endl;
for (int i = 3; i <= sqrt(1.0 * n) && n > 1; i += 2)
{
if (primes[i])
{
int ss = sum(i);
while (n % i == 0 && n > 1)
{
s += ss;
n /= i;
}
}
}
if (n > 1)
s += sum(n);
//cout << "break two" << endl;
//cout << n << endl;
//cout << s << endl;
if (s == record)
return true;
return false;
}

void solve(int n)
{
while (++n)
{
//cout << n << endl;
if (!isPrime(n) && check(n))
{
cout << n << endl;
return;
}
}
}

int main(int argc, char* argv[])
{
//freopen("input.in", "r", stdin);
//freopen("output.out", "w", stdout);
int k;
cin >> k;
gen_primes();
while (k--)
{
int n;
cin >> n;
//check(n + 1);
solve(n);
}
//fclose(stdin);
//fclose(stdout);
return 0;
}