Technical Article

Optimized prime number generator

,

This a modification to the script given by Preethi.
It generates prime numbers to the upper bound you specify.
Modifications are using following facts from algebra:
1. All prime numbers greater than 3 can be written in the form 6 * X +/- 1.
2. Instead of checking the module for ALL numbers <= FLOOR(SQRT(@aX)), it is enough to check PRIME NUMBERS ONLY.
Also, the check is done using SQL on @Prime table, instead of a WHILE-loop.

Set NOCOUNT ON
DEclare @Prime Table
(PrimeN bigint NOT NULL PRIMARY KEY)

DECLARE
@aX bigint,
@aY bigint,
@Div bit,
@Temp bigint,
@increment tinyint

insert into @Prime values (2)
insert into @Prime values (3)

SET @aX =  5
SET @increment = 2
WHILE @aX <= 100000 --Here is the upper bound
BEGIN
  if not exists (select top 1 null from @Prime
             where (PrimeN <= FLOOR(SQRT(@aX))) and (@aX % PrimeN = 0))

    INSERT INTO @Prime VALUES (@aX)

SET @aX=@aX+@increment
  set @increment = 6 - @increment
END

SELECT * FROM @Prime

Rate

You rated this post out of 5. Change rating

Share

Share

Rate

You rated this post out of 5. Change rating