supongamos que desea encontrar todos los números primos desde 999990000 hasta 1000000000. Podría usar un enfoque ingenuo (fuerza bruta) pero eso le daría un poco de tiempo. Entonces te das cuenta de que podrías usar un tamiz de erathothenes pero te quedarás sin espacio en el montón ya que tendrías que crear una matriz de enteros 1000000000.
Tamiz segmentado resuelve el problema anterior con la misma complejidad de tiempo que un tamiz pero utilizando menos memoria. El tamiz segmentado utiliza la diferencia de los números (1000000000-999990000 = 10000).
Para implementar un tamiz segmentado, primero debe encontrar todos los números primos menores que [math] \ [/ math] sqrt 1000000000.
- ¿Cuáles son las partes fáciles de la informática y cuáles son las partes difíciles?
- ¿Cuál es el criterio de elección para el desarrollo de algoritmos recursivos o iterativos?
- Cómo insertar un nuevo nodo en un árbol binario (no buscar árbol binario)
- ¿Cuál es la diferencia principal entre algoritmo y pseudocódigo?
- Cómo mostrar un problema es NP completo
luego recorre todos los números desde 999990000 hasta 1000000000. Y comprueba si son divisibles por cualquiera de los números primos encontrados en el primer paso. para hacer esto tu
tiene que encontrar el número más bajo divisible por el primo en el rango. Y luego marque los valores en la bandera [] incrementando el valor más bajo.
Para obtener más información, consulte mi blog:
Tamiz segmentado de erathothenes (SPOJ PRIME1)
EDITAR: tenga en cuenta que el segundo paso podría optimizarse.
