Fork me on GitHub

teddy online judge

teddy es un oso de peluche

909. La criba de Eratóstenes

Limite de tiempo : 2 seg.   Total runs : 96  Aceptados : 10

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.

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

Hecho por Alan Gonzalez @_alanboy ; Concepto Luis Hector Chavez @lhchavez ; Infraestructura por Instituto Tecnologico de Celaya

contribuciones de los usuarios bajo la licencia cc-wiki con atribucion requerida