1. C, Doina Logofatu


/**
* ACM programming Contest WS 08/09
* 10042 Smith Numbers
* UVa Status: AC, 14 Dec. 2008
* Run Time: 0.310
* Programming Language: C
* @author Doina Logofatu logofatu@hm.edu
* link: http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=8&category=12&page=show_problem&problem=983
*/


#include <stdio.h>
#include <math.h>

int quersumme(int n){
int s = 0;
while(n){
s += n%10;
n /= 10;
}
return s;
}

int quersummeZerlegung( int n){
int s = 0;
int k;
int sqrt_n = (int)sqrt(n);
while(n%2==0) { s += 2; n /= 2;}
for(k=3; n>1 && k<= sqrt_n; k+=2)
while(n%k==0) { s += quersumme(k); n /= k;}
if(n != 1) s += quersumme(n);
return s;
}

int prim( int n){
int i, sqrt_n;
if(n<2) return 0;
if(n==2) return 1;
if(n%2 == 0) return 0;
sqrt_n = (int)sqrt(n);
for(i=3; i<=sqrt_n; i+=2)
 if(n%i==0) return 0;
return 1;

}

int main() {
int cases;
int n, k;
int found;
scanf("%d", &cases);
while(cases){
scanf("%d", &n);
found = 0;
for(k = n+1; !found; k++)
if(!prim(k) && quersumme(k)== quersummeZerlegung(k)){
printf("%d\n", k);
found = 1;
}
cases--;
}
return 0;
}