Saltar al contenido

Imprimir números primos con consulta SQL

Luego de de nuestra extensa compilación de datos solucionamos esta dificultad que pueden tener muchos de nuestros lectores. Te compartimos la solución y nuestro objetivo es servirte de mucha ayuda.

Solución:

En PostgreSQL, probablemente la consulta más rápida que imprime números primos hasta 1000 es:

SELECT regexp_split_to_table('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,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997',E',')::int
AS x
;

Tomó solo 16 ms en mi computadora.

  • Nota: se copió una lista de números primos de https://en.wikipedia.org/wiki/Prime_number

    y pegado en este largo string

Si prefiere SQL, entonces esto funciona

WITH x AS (
  SELECT * FROM generate_series( 2, 1000 ) x
)
SELECT x.x
FROM x
WHERE NOT EXISTS (
  SELECT 1 FROM x y
  WHERE x.x > y.x AND x.x % y.x = 0
)
;

Es dos veces más lento: 31 ms.


Ans una versión equivalente para Oracle:

WITH x AS(
    SELECT level+1 x
    FROM dual
    CONNECT BY LEVEL <= 999
)
SELECT x.x
FROM x
WHERE NOT EXISTS (
  SELECT 1 FROM x y
  WHERE x.x > y.x AND remainder( x.x, y.x) = 0
)
;

La mejora más obvia es que, en lugar de verificar de 1 a n, puede verificar de 1 a la raíz cuadrada de n.

Una segunda optimización importante sería usar una tabla temporal para almacenar los resultados y verificarlos primero. De esta manera, puede iterar de forma incremental de 1 a n, y solo verificar los números primos conocidos de 1 a la raíz cuadrada de n (haciendo eso recursivamente hasta que tenga una lista). Si hace las cosas de esta manera, probablemente querrá configurar la detección de números primos en una función y luego hacer lo mismo con su generador de series numéricas.

Sin embargo, ese segundo significa extender SQL, por lo que no sé si eso se ajusta a sus requisitos.

Para postgresql usaría generate_series ir a generar la lista de números. Luego crearía funciones que luego almacenarían la lista de números primos en una tabla temporal o los pasarían de nuevo dentro y fuera de forma ordenada. array y luego juntarlos así

MariaDB (con complemento de secuencia)

Similar al algoritmo de kordirkos:

select 2 as p union all
select n.seq
from seq_3_to_1000_step_2 n
where not exists (
    select 1
    from seq_3_to_32_step_2 q
    where q.seq < n.seq
      and n.seq mod q.seq = 0
);

Usando la UNIÓN IZQUIERDA:

select 2 as p union all
select n.seq
from seq_3_to_1000_step_2 n
left join seq_3_to_32_step_2 q
      on  q.seq < n.seq
      and n.seq mod q.seq = 0
where q.seq is null;

mysql

No hay ayudantes de generación de secuencias en MySQL. Entonces, las tablas de secuencia deben crearse primero:

drop temporary table if exists n;
create temporary table if not exists n engine=memory
    select t2.c*100 + t1.c*10 + t0.c + 1 as seq from 
    (select 0 c union all select 1 c union all select 2 c union all select 3 c union all select 4 c union all select 5 c union all select 6 c union all select 7 c union all select 8 c union all select 9 c) t0,
    (select 0 c union all select 1 c union all select 2 c union all select 3 c union all select 4 c union all select 5 c union all select 6 c union all select 7 c union all select 8 c union all select 9 c) t1,
    (select 0 c union all select 1 c union all select 2 c union all select 3 c union all select 4 c union all select 5 c union all select 6 c union all select 7 c union all select 8 c union all select 9 c) t2
    having seq > 2 and seq % 2 != 0;

drop temporary table if exists q;
create temporary table if not exists q engine=memory
    select *
    from n
    where seq <= 32;
alter table q add primary key seq (seq);

Ahora se pueden usar consultas similares:

select 2 as p union all
select n.seq
from n
where not exists (
    select 1
    from q
    where q.seq < n.seq
      and n.seq mod q.seq = 0
);

select 2 as p union all
select n.seq
from n
left join q
    on  q.seq < n.seq
    and n.seq mod q.seq = 0
where q.seq is null;

sqlfiddle

Agradecemos que quieras estimular nuestro ensayo fijando un comentario y puntuándolo te estamos agradecidos.

¡Haz clic para puntuar esta entrada!
(Votos: 0 Promedio: 0)



Utiliza Nuestro Buscador

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *