teddy online judge

909. La criba de Eratóstenes

Limite de tiempo : 2 seg.   Total runs : 102  Aceptados : 12

Eratóstenes de Cirene fue un matemático griego que vivió alrededor del año 250 antes de Cristo. También fue un atleta con intereses en la poesía, la geografía, la astronomía, y la música.

La criba de Eratóstenes es un algoritmo para encontrar todos los números primos menores que un número, hace esto eliminando sucesivamente todos los múltiplos de los números ya conocidos por ser primos. La figura siguente ilustra el método en los números menores a 102.

Para ver lo que está pasando, sugiero construir el diagrama por uno mismo. Comienza con la rejilla sin tachaduras, solo los numeros del 1 al 102.

• Omite el 1 porque es una unidad.
• El siguiente número es 2, por lo que es primo. Tacha todos los múltiplos de 2: éstos se encuentran en las líneas horizontales a partir de 4, 6 y 8.
• El siguiente número no tachado es 3, por lo que es primo. Tacha todos los múltiplos de 3: éstos se encuentran en las líneas horizontales a partir de 6, ya se cruza hacia fuera, y 9.
• El siguiente número no tachado es 5, por lo que es primo. Tacha todos los múltiplos de 5: éstos se encuentran en las líneas diagonales inclinadas hacia arriba y hacia la derecha, a partir de las 10.
• El siguiente número no tachado es 7, por lo que es primo. Tacha todos los múltiplos de 7: éstos se encuentran en las líneas diagonales inclinadas hacia abajo y hacia la derecha, a partir de las 14.
• El siguiente número no tachado es 11, por lo que es primo. El primer múltiplo de 11 que aún no ha sido tachado porque tiene un divisor más pequeño es de 121, lo que está fuera de la imagen, así que ahí nos detenemos.

Los números restantes (sombreados) son los números primos, en este caso: 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 y 101.

La criba de Eratóstenes no es sólo una curiosidad histórica; es todavía uno de los métodos más eficaces conocidos para la fabricación de una extensa lista de números primos

Escribe un programa que calcule listas de numeros primos utilizando una criba de Eratótenes.

Entrada

La primer linea es un numero c que incluye el numero de casos a seguir. Las siguientes c lineas son definiciones de tamaños de cribas. En el ejemplo de arriba, la criba de erastotenes tenia dimensiones de 17 columnas y 6 renglones.

Salida

Construye una criba con las dimensiones dadas y por cada caso imprime Caso c : seguido e la lista de numeros primos que pudiste calcular y donde c es el numero de caso actual iniciando de 1. Depues de la lista, imprime la criba que construiste, marcando con * los numeros que no son primos y dejando un espacio de 4 caracteres para cada numero.

Restricciones

0 < c < 50
0 < columnas ≤ 100
0 < renglones ≤ 100

Entrada de ejemplo

2
17 6
5 5

Salida de ejemplo

Caso 1 : 1 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 101
   1   7  13  19   *  31  37  43   *   *  61  67  73  79   *   *  97
   2   *   *   *   *   *   *   *   *   *   *   *   *   *   *   *   *
   3   *   *   *   *   *   *   *   *   *   *   *   *   *   *   *   *
   *   *   *   *   *   *   *   *   *   *   *   *   *   *   *   *   *
   5  11  17  23  29   *  41  47  53  59   *  71   *  83  89   * 101
   *   *   *   *   *   *   *   *   *   *   *   *   *   *   *   *   *
Caso 2 : 1 2 3 5 7 11 13 17 19 23
   1   *  11   *   *
   2   7   *  17   *
   3   *  13   *  23
   *   *   *  19   *
   5   *   *   *   *

_{Alan Gonzalez para el Concurso Local de Programación del Tecnológico de Celaya Febrero 2016}