Una clásica tarea de programación es encontrar todos los números primos menores por debajo de una cantidad introducida por el usuario. El algoritmo más básico consiste en usar una versión digital de la criba de Eratóstenes que es bastante simple de escribir pero puede volverse muy lenta conforme se incrementa el la cantidad que introduce el usuario. El código en este post es básicamente el algoritmo la criba de Eratóstenes con unas cuantas optimizaciones. En mi PC es posible encontrar todos los números primos menores a 10,000,000 relativamente rápido usando este código. Para los números primos menores a 100,000,000 el código se tarda casi un minuto en mi PC. Para números mayores el tiempo se multiplicaría considerablemente.

El código para encontrar los números primos es el siguiente (lo siento, no pude lograr que wordpress formateara el código correctamente):

public static ArrayList<Integer> numerosPrimos(int max) {
    ArrayList<Integer> primos = new ArrayList<Integer>();
    primos.add(2);

    for (int i = 3; i < max; i++) {
        boolean es_primo = true;
        double limite = Math.ceil(Math.sqrt(i));
        for (int j = 0; j < primos.size(); j++) {
             if (i % primos.get(j) == 0) {
                 es_primo = false;
                 break;
             }
             if (primos.get(j) > limite) break;
        }
        if (es_primo) primos.add(i);
    }

    return primos;
}

He agregado este método a la clase TareasProgramacion en github. Se puede usar este método como en el siguiente ejemplo:

import java.util.*;
import org.monstruosoft.utils.*;

public class Prueba {
    public static void main(String args[]) {
        Scanner s = new Scanner(System.in);
        System.err.print("Escribe el número máximo para la búsqueda de números primos: ");
        int max = s.nextInt();
        ArrayList primos = TareasProgramacion.numerosPrimos(max);
        for (Integer i: primos)
            System.out.println(i);
        System.out.println("Se encontraron " + primos.size() + " números primos menores a " + max + ".");
    }
}

Al ejecutar el programa obtenemos la siguiente salida:

monstruosoft@debian:~/code/monstruosoft/java-utils$ java Prueba 
Escribe el número máximo para la búsqueda de números primos: 100
2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97
Se encontraron 25 números primos menores a 100.

El código Java para esta tarea es prácticamente idéntico al código C del post anterior, sólo tenemos que ponerlo dentro de un método de una clase. En este caso podemos usar la clase TareasProgramación que ya hemos usado en posts anteriores.

public class TareasProgramacion {
    private static final String ROMANOS_UNIDADES[] = {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};
    private static final String ROMANOS_DECENAS[]  = {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};
    private static final String ROMANOS_CENTENAS[] = {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};
    private static final String ROMANOS_MILES[]    = {"", "M", "MM", "MMM"};

    public static String cantidadNumerosRomanos(String s) {
        StringBuilder result = new StringBuilder();
        BigDecimal totalBigDecimal = new BigDecimal(s).setScale(2, BigDecimal.ROUND_DOWN);
        long parteEntera = totalBigDecimal.toBigInteger().longValue();

        if (parteEntera  3999)
            throw new IllegalArgumentException("El número a convertir debe estar entre 1 y 3999.");

        int m = (int)parteEntera / 1000, c = (int)(parteEntera % 1000) / 100, d = (int)(parteEntera % 100) / 10, un = (int)parteEntera % 10;
        result.append(ROMANOS_MILES[m]);
        result.append(ROMANOS_CENTENAS[c]);
        result.append(ROMANOS_DECENAS[d]);
        result.append(ROMANOS_UNIDADES[un]);

        return result.toString();
    }
}

Una ejecución de un programa de prueba para el código anterior luce como la siguiente:

Escribe un número entre 1 y 3999: 
12
XII
Escribe un número entre 1 y 3999: 
1999
MCMXCIX
Escribe un número entre 1 y 3999: 
2018
MMXVIII
Escribe un número entre 1 y 3999: 
3888
MMMDCCCLXXXVIII
Escribe un número entre 1 y 3999: 
3999
MMMCMXCIX

Para obtener el código completo visita el repositorio de github de monstruosoft.

En este post escribiremos una clase de Java que nos permita convertir un número a su representación escrita en forma de texto. Existen algunas alternativas en español pero las que he revisado tienen límites muy pequeños como convertir sólo números entre 0 y 100, o tienen límites arbitrarios como 999,999,999¹ sin ninguna razón aparente. Además, ya sabemos que me gusta hacer las cosas yo mismo 😛 . El código de este post puede convertir cualquier entero positivo de tipo int en el rango de 0 a 2,147,483,647 y, en teoría, cualquier número entero menor a 1,000,000,000,000 que debería ser suficiente en la mayoría de los casos 😛 :

Read More