Jugando con números primos

Anoche después de estar en un cumpleaños con uno de esos Nerds que todavía quedan dando vueltas por el mundo, surgió una duda… cuantos números primos han entre el 1 y el 500… Capas que con tiempo lo sacas, pero con tres cervezas arriba no podía distinguir si el 1 era un número primo o no ;P

Entonces esta mañana, ya más fresco, me puse a buscar la manera de hacerlo y me encontré con muchísimos ejemplos, todos basados en el método de calcular número por número.

-- Jugando con Numeros primos, Metodo clasico, 
-- escolar, fuerza bruta, metodico, aburrido ;P

set nocount on
declare @start datetime
DECLARE
    @i INT,
    @a INT,
    @count INT
set @start = getdate()
SET @i = 1
WHILE (@i < = 500)
    BEGIN
        SET @count = 0
        SET @a = 1
        WHILE (@a < = @i)
            BEGIN
                IF (@i % @a = 0) 
                    SET @count = @count + 1
                SET @a = @a + 1
            END
        IF (@count = 2) 
            PRINT @i
        SET @i = @i + 1
    END 

select datediff(ms, @start, getdate() )
-- 2073 

Este método, demora unos 2 segundos en la tarea, básicamente una eternidad en tiempos de cálculo y resulta de lo más anti rendimiento que se te pueda ocurrir
Pero, profundizando un poco más, y recordando lo altamente performante que es un JOIN, empecé a hacer unas pruebas y son una pequeña sugerencia de mis compañeros de la ofi… si acá también llegaron los nerds, me recordaron el teorema del resto, su aplicación práctica y el operando informático por ciento (%); todo esto y un poco de maña nos da como resultado:

-- Jugando con Numeros primos, Metodo Rock & Roll, Experto, Nerd ;P

create table #Numbers (Number smallint identity primary key);
go
insert into #Numbers default values;
go 500 -- Mete 500 registros... ¿un TIP...? ¡Naa!
declare @start datetime
set @start = getdate()
select N1.Number
from #Numbers N1
inner join #Numbers N2
        on N1.Number % N2.Number = 0  --> % -> Que simbolo raro, dale al F1  
group by N1.Number
having count(*) <= 2
order by N1.Number; 

drop table #Numbers 

select datediff(ms, @start, getdate() )
-- 90

Con un abrumador resultado de 90 milisegundos contra los 2070 del primer método… nada mas que decir ¿no? saquen sus conclusiones, INNER JOIN WINS!