Copiado al portapapeles
Descripción
Se tienen los numeros naturales entre dos valores mınimo y maximo. Por ejemplo consideremos
los numeros que estan entre 14 y 19 inclusive. Estos son: (14, 15, 16, 17, 18, 19).
Nos piden construir un grafo donde cada numero representa un nodo. Se coloca una arista
entre cada par de nodos cuya suma sea un numero primo. Se coloca una arista que va del nodo
11 al 12, cuya suma es 23 que efectivamente es un numero primo. el grafo que se forma es el
siguiente:
Como se ve solo, se han utilizado los numeros 14, 15, 16, 17 que son parte de este grafo. Si
repetimos el proceso con los numeros restantes obtendremos el grafo:
De esta forma se han obtenido 2 grafos conexos.
Dados los valores de mınimo y maximo se pide hallar cuantos grafos conexos existen.
Entrada
La entrada consiste de multiples casos de prueba. Cada caso de prueba consiste de dos numeros
1 ≤ minimo, maximo ≤ 1000. La entrada termina con 0 0.
Salida
Escriba una linea, por cada caso de prueba, el numero de grafos conexos que se forman.
Ejemplo Entrada
14 19 10 19 1 19 0 0
Ejemplo Salida
2 1 1
Ayuda
Tome en cuenta que si el rango dado es 1...1000 entonces la maxima suma de dos numeros en ese intervalo es 1999, que casualmente es primo :D
Utilize el metodo de la criba para detectar si un numero es primo en O(1), o sino utilizar un metodo con complejidad O(raiz de N).