~cpp
// no10042 - Smith Numbers
#include <iostream>
#include <cmath>
using namespace std;
void find_smith_number(int n);
int sum_digit_prime_factor(int n);
int sum_digit_number(int n);
int main()
{
int nCase;
int i;
int number;
cin >> nCase;
for (i = 0; i < nCase; i++)
{
cin >> number;
find_smith_number(number);
}
return 0;
}
void find_smith_number(int n)
{
int i;
for (i = n + 1; ;i++)
{
if (sum_digit_number(i) == sum_digit_prime_factor(i))
break;
}
cout << i << endl;
}
int sum_digit_number(int n)
{
int sumDigitNumber = 0;
int temp = n;
do {
sumDigitNumber += temp % 10;
temp /= 10;
} while (temp != 0);
return sumDigitNumber;
}
int sum_digit_prime_factor(int n)
{
int i;
int sumDigitPrimeFactor = 0;
int temp = n;
while (temp % 2 == 0)
{
temp /= 2;
sumDigitPrimeFactor += 2;
}
i = 3;
while (i <= sqrt(temp) + 1)
{
if (temp % i == 0)
{
sumDigitPrimeFactor += sum_digit_number(i);
temp /= i;
}
else
i += 2;
}
if (sumDigitPrimeFactor == 0 || n == 2)
return -1;
if (temp > 1)
sumDigitPrimeFactor += sum_digit_number(temp);
return sumDigitPrimeFactor;
}