Como otros escribieron, existen algoritmos bien conocidos y simples para encontrar todos los números primos hasta un número n (imprimir todos los números primos no es más factible que imprimir todos los números, ya que son infinitos).
Un algoritmo muy simple y efectivo se llama Tamiz de Eratóstenes . En una implementación simple, se inicializa una matriz de elementos n-1 con números del 2 al n. Luego, el algoritmo comienza con el primer elemento (2), el elemento se imprime como primo y todos sus múltiplos se marcan como no primos en la matriz. Luego buscamos el siguiente elemento no marcado (3), lo imprimimos como primo y marcamos todos los múltiplos como no primos. Luego llegamos al siguiente elemento sin marcar (5) … y así sucesivamente.
En cuanto a “para qué podría usarse”, es posible que desee comprobar esta respuesta de Quora.
- ¿En qué se diferencia un árbol de búsqueda binario de un árbol binario?
- ¿Cuál es el mejor algoritmo para calcular automáticamente un puntaje de crédito?
- ¿Cuál es la diferencia entre la altura y la profundidad de un árbol?
- ¿Cuál es el enfoque más eficiente para resolver problemas de factorización media en SPOJ?
- Para una computadora, ¿qué tan aleatorio es ser aleatorio?
Para su última parte de la pregunta … sí, es posible tener un algoritmo. Sin embargo, no existen algoritmos conocidos que permitan la factorización de números (un problema equivalente a encontrar si un número es primo) en una “cantidad de tiempo razonable” para números grandes.
