Check if a number is prime or not in mysql

Question

I am wondering what's the best way to check whether a number is prime or not using sql. I was able to generate the sequence of numbers from 1 to 1000 but I would like to identify which number is a prime. Can somebody share your thoughts on this.Thanks.

SELECT i 
  FROM
(
select
     i0.i
    +i1.i*2
    +i2.i*4
    +i3.i*8
    +i4.i*16
    +i5.i*32
    +i6.i*64
    +i7.i*128
    +i8.i*256
    +i9.i*512
    as i
from
               (select 0 as i union select 1) as i0
    cross join (select 0 as i union select 1) as i1
    cross join (select 0 as i union select 1) as i2
    cross join (select 0 as i union select 1) as i3
    cross join (select 0 as i union select 1) as i4
    cross join (select 0 as i union select 1) as i5
    cross join (select 0 as i union select 1) as i6
    cross join (select 0 as i union select 1) as i7
    cross join (select 0 as i union select 1) as i8
    cross join (select 0 as i union select 1) as i9
) Z
WHERE i>=1 AND i<=1000;

Answer 1

You can use a self join to check for primes from the table of generated numbers. Primes have 2 factors, a conditional check would be sufficient.

select val
from (select x.val,x1.val as divisor,mod(x.val,x1.val) as remaindr
      from x
      join x x1 on x1.val <= x.val
     ) t
group by val
having sum(case when remaindr = 0 then 1 else 0 end) = 2

Sample Demo

An optimization for the above is to check for divisors in the range of 1 to sqrt(number). In that case the only factor for a prime number would be 1, and the conditional check can be changed accordingly.

select val
from (select x.val,x1.val as divisor,mod(x.val,x1.val) as remaindr
      from x
      join x x1 on x.val >= pow(x1.val,2)
      where x.val > 1 --excluding 1 as it is neither prime nor composite
     ) t
group by val
having sum(case when remaindr = 0 then 1 else 0 end) = 1

Answer 2

This is not a good fit for SQL. But you can do it as:

select n.*
from n
where not exists (select 1
                  from n n2
                  where n2.n <= sqrt(n.n) and n2.n > 1 and
                        n.n mod n2.n = 0
                 ) and
      n > 1;  -- 1 is deemed to not be prime

You may need to wait a little while to start seeing numbers.

I should note that in MySQL, a shorter way to generate the numbers is:

select (@rn := @rn + 1) as i
from (select 0 as i union select 1) as i0 cross join
     (select 0 as i union select 1) as i1 cross join
     (select 0 as i union select 1) as i2 cross join
     (select 0 as i union select 1) as i3 cross join
     (select 0 as i union select 1) as i4 cross join
     (select 0 as i union select 1) as i5 cross join
     (select 0 as i union select 1) as i6 cross join
     (select 0 as i union select 1) as i7 cross join
     (select 0 as i union select 1) as i8 cross join
     (select 0 as i union select 1) as i9 cross join
     (select @rn := 0) params
having i >= 1 and i <= 1000;

This should be faster because no intermediate table is materialized. In addition, adding 1 is probably slightly faster than the arithmetic, although the difference is calculation may be rather small.