jueves, diciembre 16, 2010

Números de Smith - Problema UVA 10042

Básicamente, este problema busca encontrar números en los que la suma de sus dígitos sea igual a la suma de sus factores primos. El enunciado está en el enlace http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=983

import java.io.*;

class Main {
    static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String args[]) throws Exception {
        Main myWork = new Main();   // create a dinamic instance
        myWork.Begin();             // the true entry point
    }

    public int sumaDivisores(int n) {
        double raiz = Math.sqrt(n);
        int tmp = n;
        int respuesta=0;
        while(n%2==0) { respuesta+=2; n>>=1; }
        for(int i=3; i<=raiz; i+=2) {
            if(n%i==0) {
                respuesta+=sumaDigitos(i);
                n = n/i;
                i-=2;
            }
        }
        if(n!=tmp && n!=1) respuesta+=sumaDigitos(n);
        return respuesta;
    }

    public int sumaDigitos(int n) {
        int respuesta=0;
        while(n>0) {
            respuesta+=(n%10);
            n = n/10;
        }
        return respuesta;
    }

    public boolean esPrimo(long n) {
        double raiz = Math.sqrt(n);
        if(n==2) return true;
        if(n%2==0) return false;
        for(int i=3; i<=raiz; i+=2) if(n%i==0) return false;
        return true;
    }

    void Begin() throws Exception {
        int cont = 0;
        int numeroCasos = Integer.parseInt(in.readLine());
        while(cont<numeroCasos) {
            int numero = Integer.parseInt(in.readLine());
            while(true) {
                numero++;
                if(esPrimo(numero)) continue;
                if(sumaDigitos(numero)==sumaDivisores(numero)) {
                    System.out.println(numero);
                    cont++;
                    break;
                }
            }
        }
    }
}

1 comentario:

Multiprocesamiento recursivo en JAVA 7

Una de las estrategias de diseño de algoritmos más comunes es la de "divide y vencerás", en la cual, un problema de tamaño relativ...