Podría ser una recursión que se va pasando una lista de primos, arrancas con 2,3, y 5 ponele, si ninguno de los tres lo dividie ese numero es primo y lo agregas a la lista y así vas avanzando hasta el numero x que queres. Podes ya determinar que es primo en el mayor a raiz de x. Si es primo lo agregas a la lista y después consulta si esta en la lista.