1.

/**
* FWP, Ausgewaehlte Probleme aus dem ACM Programming Contest, SS10
* Problem: 10042 - Smith Numbers
* Link: http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=10042
*
* @author Michael Haus
* @version 1.0, 03/08/2010
*
* Method : arithmetic
* Status : Accepted
* Runtime: 1.520
*/

import java.util.Scanner;
import java.math.BigInteger;

public class Main {

public static void main(String[] args){

Scanner input = new Scanner(System.in);
int i = input.nextInt();

while(i >= 1){
boolean found = false;
int n = input.nextInt();
n++;

while(!found){
if(isPrime(n)){
n++;
} else {
int sumPrimes = sumPrimefactors(n);
int sumDigits = sumDigits(n);

if(sumPrimes == sumDigits){
System.out.println(n);
found = true;
i--;
} else {
n++;
}
}
}
}
}

public static int sumPrimefactors(int n){
int sumPrimes = 0;
while(n != 1){
int factor = factor(n);
if(factor < 10){
sumPrimes += factor;
} else {
sumPrimes += sumDigits(factor);
}
n /= factor;
}
return sumPrimes;
}

private static int factor(int n){
if(n % 2 == 0)
return 2;
if(n % 3 == 0)
return 3;
for(int k = 5; k*k <= n; k += 6){
for(int b = k; b <= k+2; b+=2){
while(n % b == 0){
return b;
}
}
}
return n;
}

public static int sumDigits(int n){
int sumDigits = 0;
do{
sumDigits += n%10;
n /= 10;
} while(n > 0);
return sumDigits;
}

public static boolean isPrime(int n){
BigInteger big = new BigInteger(Integer.toString(n));
boolean result = big.isProbablePrime(1);
return result;
}
}

2.


/**
* Angewandte Mathematik, SS09, IFB 2C
* ACM Problem #10042 (Smith Numbers)
* http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=8&category=12&page=show_problem&problem=983
*
* @author Marcel Sachse
* @author Fabian Seidl
* @version 1.0, 31.03.2009
*
* Status : Accepted
* Runtime: 1.050
*/


import java.io.BufferedInputStream;
import java.util.Scanner;


public class Main {

public static void main(String[] args)

{
BufferedInputStream bin = new BufferedInputStream(System.in);
Scanner scanner = new Scanner(bin);

int counter = scanner.nextInt();
for (int i=0;i<counter;i++)
{
int zahl=scanner.nextInt();
while(true)
{
zahl++;
// vergleichen der Quersummen der zahl und der primzahlfakturen
if(qSum(zahl)==qPrimFakt(zahl))break;
}
System.out.println(zahl);
}
scanner.close();
}

private static int qPrimFakt(int zahl)
{
int i=2;
int sum=0;
// es gibt nur primzahlfakturen unter der wurzel der zahl
double abbruch = Math.sqrt(zahl);
while(zahl>1)
{
while(true)
{
if(i>abbruch)i=zahl;
// überprüfen ob eine zahl teiler und primzahl ist
if( (zahl%i)==0 && isPrim(i))
{
zahl/=i;
break;
}
i++;
}
//quersumme der primfaktoren

//wenn die summe null ist und i gleich ein haießt das,
//das die zahl nur einen faktur hat und zwar sich selber
if (sum==0 && zahl==1)sum=-1;
// aufaddieren der quersumme der primfakturen
else sum+=qSum(i);
}
return sum;
}
// quersumme berechnen
public static int qSum(int zahl)
{
int sum =0;
while(zahl>0)
{
sum+= zahl%10;
zahl/=10;
}
return sum;

}

private static boolean isPrim(int number)
{

if (number < 2) {
return false;
//überprüfen ob es die primzahl 2 ist
} else if (number == 2)
{
return true;
} else {
// überprüfen ob die zahl ein fielfaches der 2 ist
if (number % 2 == 0) {
return false;
}
// alle ungeraden zahlen ab 3 prüfen bis zur wurzel der zahl
for (int i = 3; i <= Math.sqrt(number); i = i + 2)
{
//Teilertest
if (number % i == 0)
{
return false;
}
}
return true;
}
}
}

3. C


/**
* 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;
}