# Calculating Prime Numbers With One Query

• Comments posted to this topic are about the item Calculating Prime Numbers With One Query

• My question would be... why do you use a resource intensive, slow as a While loop recursive CTE as your sequence generator?  There are many better methods.  See the following article.

https://www.sqlservercentral.com/articles/hidden-rbar-counting-with-recursive-ctes

--Jeff Moden

RBAR is pronounced "ree-bar" and is a "Modenism" for Row-By-Agonizing-Row.
First step towards the paradigm shift of writing Set Based code:
________Stop thinking about what you want to do to a ROW... think, instead, of what you want to do to a COLUMN.

Change is inevitable... Change for the better is not.

How to post code problems
How to Post Performance Problems
Create a Tally Function (fnTally)

• I wrote this SQL Server table valued function a few years ago. It returns all the prime numbers less than 1 million in about 1 second.

Fast Table Valued Function to return all prime numbers within a range

• Calculate these once and store them in a table - look them up when needed :)_

• For exhaustive methods it's quicker to only look at odd numbers.  There was a Youtube video a little while ago where they compared all different programming languages to determine which is the "fastest" at generating primes.  SQL was pretty much in last place

The overall leaders (java, c++, rust, etc) are like 5k primes/sec.  I came up with this code to mess around and find out.  Iirc it was around 300/sec versus the contest entry (which someone did in SQLlite) was around 30/sec.  10x better but still nearly last.  Interpreted languages are inherently slower.  The generated counts are off by 1 (vs known counts) because the query count omits 2, the only even prime

`/* insert into known_prime_counts values     (10,4),    (100,25),    (1000,168),    (10000,1229),    (100000,9592),    (1000000,78498),    (10000000,664579),    (100000000,5761455) ;*/declare @n      int=10000;select count(*)--select fn.N*2+1 /*use this to return the prime numbers except for 2*/from dbo.fnTally(1, @n/2-1) fnwhere not exists(select 1                 from dbo.fnTally(1, fn.N/2) ffn                 where (fn.N*2+1)%(ffn.N*2+1)=0                        and (fn.N*2+1)<>(ffn.N*2+1));`

Aus dem Paradies, das Cantor uns geschaffen, soll uns niemand vertreiben können

• Steve Collins wrote:

For exhaustive methods it's quicker to only look at odd numbers.  There was a Youtube video a little while ago where they compared all different programming languages to determine which is the "fastest" at generating primes.  SQL was pretty much in last place

The overall leaders (java, c++, rust, etc) are like 5k primes/sec.  I came up with this code to mess around and find out.  Iirc it was around 300/sec versus the contest entry (which someone did in SQLlite) was around 30/sec.  10x better but still nearly last.  Interpreted languages are inherently slower.  The generated counts are off by 1 (vs known counts) because the query count omits 2, the only even prime

`/* insert into known_prime_counts values     (10,4),    (100,25),    (1000,168),    (10000,1229),    (100000,9592),    (1000000,78498),    (10000000,664579),    (100000000,5761455) ;*/declare @n      int=10000;select count(*)--select fn.N*2+1 /*use this to return the prime numbers except for 2*/from dbo.fnTally(1, @n/2-1) fnwhere not exists(select 1                 from dbo.fnTally(1, fn.N/2) ffn                 where (fn.N*2+1)%(ffn.N*2+1)=0                        and (fn.N*2+1)<>(ffn.N*2+1));`

You only need to test up to the square root of a number to test for primality, which is quite a saving:

`declare @n      int=100000;select fn.N*2+1 /*use this to return the prime numbers except for 2*/from dbo.fnTally(1, @n/2-1) fnwhere not exists(select 1                 from dbo.fnTally(1, sqrt(fn.N/2)) ffn                 where (fn.N*2+1)%(ffn.N*2+1)=0                        and (fn.N*2+1)<>(ffn.N*2+1));`
• Oh you're right.  This is not the final version but I'm not finding my notes on this.   Iirc if you follow the links it leads to a SQLlite script with a WHILE loop

Aus dem Paradies, das Cantor uns geschaffen, soll uns niemand vertreiben können

• Jonathan AC Roberts wrote:

You only need to test up to the square root of a number to test for primality, which is quite a saving:

`declare @n      int=100000;select fn.N*2+1 /*use this to return the prime numbers except for 2*/from dbo.fnTally(1, @n/2-1) fnwhere not exists(select 1                 from dbo.fnTally(1, sqrt(fn.N/2)) ffn                 where (fn.N*2+1)%(ffn.N*2+1)=0                        and (fn.N*2+1)<>(ffn.N*2+1));`

I did some (limited) testing using the script in the article and working up to the square root was marginally slower than working up to half the value - even though it cuts out a large proportion of the divisors. Maybe the SQRT function is slower than a simple division.

• Chris Wooding wrote:

Jonathan AC Roberts wrote:

You only need to test up to the square root of a number to test for primality, which is quite a saving:

`declare @n      int=100000;select fn.N*2+1 /*use this to return the prime numbers except for 2*/from dbo.fnTally(1, @n/2-1) fnwhere not exists(select 1                 from dbo.fnTally(1, sqrt(fn.N/2)) ffn                 where (fn.N*2+1)%(ffn.N*2+1)=0                        and (fn.N*2+1)<>(ffn.N*2+1));`

I did some (limited) testing using the script in the article and working up to the square root was marginally slower than working up to half the value - even though it cuts out a large proportion of the divisors. Maybe the SQRT function is slower than a simple division.

Really?! Can you provide your test script?

• Jonathan AC Roberts wrote:

Chris Wooding wrote:

Jonathan AC Roberts wrote:

You only need to test up to the square root of a number to test for primality, which is quite a saving:

`declare @n      int=100000;select fn.N*2+1 /*use this to return the prime numbers except for 2*/from dbo.fnTally(1, @n/2-1) fnwhere not exists(select 1                 from dbo.fnTally(1, sqrt(fn.N/2)) ffn                 where (fn.N*2+1)%(ffn.N*2+1)=0                        and (fn.N*2+1)<>(ffn.N*2+1));`

I did some (limited) testing using the script in the article and working up to the square root was marginally slower than working up to half the value - even though it cuts out a large proportion of the divisors. Maybe the SQRT function is slower than a simple division.

Really?! Can you provide your test script?

It's the one from the article with SQRT(T1.C0) replacing T1.C0 / 2.

`WITH NUMBER_SEQUENCE(C0) AS(SELECT 2 AS C0UNION ALLSELECT C0 + 1 AS C0 FROM NUMBER_SEQUENCE WHERE NUMBER_SEQUENCE.C0 < 100000)SELECT C0FROM (SELECT C0, CASE WHEN (REST <> 0 OR C0 = 2 OR C0 = 3) THEN 0 ELSE 1 END AS REST_CONDITIONFROM (SELECT T.C0 AS C0, T.C1, T.C0 % T.C1 AS RESTFROM (SELECT T1.C0 AS C0, T0.C0 AS C1FROM NUMBER_SEQUENCE AS T0, NUMBER_SEQUENCE AS T1WHERE SQRT(T1.[C0]) >= T0.C0 OR T1.C0 = 2 OR T1.C0 = 3) AS T) AS T) AS TGROUP BY C0HAVING SUM(REST_CONDITION) = 0OPTION (MAXRECURSION 0);`
• Jonathan AC Roberts wrote:

You only need to test up to the square root of a number to test for primality, which is quite a saving:

`declare @n      int=100000;select fn.N*2+1 /*use this to return the prime numbers except for 2*/from dbo.fnTally(1, @n/2-1) fnwhere not exists(select 1                 from dbo.fnTally(1, sqrt(fn.N/2)) ffn                 where (fn.N*2+1)%(ffn.N*2+1)=0                        and (fn.N*2+1)<>(ffn.N*2+1));`

That's a nice improvement.  It still seems tho when it scales to bigger search counts it slows down disproportionately

Aus dem Paradies, das Cantor uns geschaffen, soll uns niemand vertreiben können

• I think the script in the article is a bit of a non-starter.

It is calculating the square root multiple times for each row.

• Steve Collins wrote:

Jonathan AC Roberts wrote:

You only need to test up to the square root of a number to test for primality, which is quite a saving:

`declare @n      int=100000;select fn.N*2+1 /*use this to return the prime numbers except for 2*/from dbo.fnTally(1, @n/2-1) fnwhere not exists(select 1                 from dbo.fnTally(1, sqrt(fn.N/2)) ffn                 where (fn.N*2+1)%(ffn.N*2+1)=0                        and (fn.N*2+1)<>(ffn.N*2+1));`

That's a nice improvement.  It still seems tho when it scales to bigger search counts it slows down disproportionately

Each number you test for primality needs O(sqrt(n)*n) calculations, so it will slow down for larger numbers. Also, if you increase @n to 10 times its previous value each run you would expect the elapsed time to go up by a factor of over 30.

• Peter "Peso" Larsson wrote a nasty fast Prime Numbers function years ago and I tested it to confirm it.  I'll see if I can find it in my archives this week if someone else doesn't find it first.

--Jeff Moden

RBAR is pronounced "ree-bar" and is a "Modenism" for Row-By-Agonizing-Row.
First step towards the paradigm shift of writing Set Based code:
________Stop thinking about what you want to do to a ROW... think, instead, of what you want to do to a COLUMN.

Change is inevitable... Change for the better is not.

How to post code problems
How to Post Performance Problems
Create a Tally Function (fnTally)

• Jeff Moden wrote:

Peter "Peso" Larsson wrote a nasty fast Prime Numbers function years ago and I tested it to confirm it.  I'll see if I can find it in my archives this week if someone else doesn't find it first.

`/*Sieve Of Atkin implementationPeter LarssonRyan Randall*/-- Initialize user supplied parameterDECLARE @MaxPrime INTSET @MaxPrime = 1000000-- Prepare helper variablesDECLARE @MaxNumber INTSET @MaxNumber = SQRT(@MaxPrime)-- Create staging tablesCREATE TABLE #Primes(Prime INT NOT NULL,Prime2 BIGINT NOT NULL)CREATE TABLE #Sequence(Seq INT NOT NULL,Seq2 BIGINT NOT NULL)CREATE UNIQUE CLUSTERED INDEX IX_Sequence ON #Sequence (Seq, Seq2)INSERT #Sequence(Seq,Seq2)SELECT n,CAST(n AS BIGINT) * CAST(n AS BIGINT)FROM (SELECT 1+ 1000 * COALESCE(d.Digit, 0)+ 100 * COALESCE(c.Digit, 0)+ 10 * COALESCE(b.Digit, 0)+ COALESCE(a.Digit, 0) AS nFROM (SELECT 0 AS Digit UNION ALLSELECT 1 UNION ALL SELECT 2 UNION ALL SELECT 3 UNION ALLSELECT 4 UNION ALL SELECT 5 UNION ALL SELECT 6 UNION ALLSELECT 7 UNION ALL SELECT 8 UNION ALL SELECT 9) AS aLEFT JOIN (SELECT 0 AS Digit UNION ALLSELECT 1 UNION ALL SELECT 2 UNION ALL SELECT 3 UNION ALLSELECT 4 UNION ALL SELECT 5 UNION ALL SELECT 6 UNION ALLSELECT 7 UNION ALL SELECT 8 UNION ALL SELECT 9) AS b ON @MaxNumber > 10AND 10 * b.Digit < @MaxNumberLEFT JOIN (SELECT 0 AS Digit UNION ALLSELECT 1 UNION ALL SELECT 2 UNION ALL SELECT 3 UNION ALLSELECT 4 UNION ALL SELECT 5 UNION ALL SELECT 6 UNION ALLSELECT 7 UNION ALL SELECT 8 UNION ALL SELECT 9) AS c ON @MaxNumber > 100AND 100 * c.Digit < @MaxNumberLEFT JOIN (SELECT 0 AS Digit UNION ALLSELECT 1 UNION ALL SELECT 2 UNION ALL SELECT 3 UNION ALLSELECT 4 UNION ALL SELECT 5 UNION ALL SELECT 6 UNION ALLSELECT 7 UNION ALL SELECT 8 UNION ALL SELECT 9) AS d ON @MaxNumber > 1000AND 1000 * d.Digit < @MaxNumberWHERE a.Digit < @MaxNumber) AS qWHERE n <= @MaxNumberORDER BY nINSERT #Primes(Prime,Prime2)SELECT 2 AS k, 4 UNION ALLSELECT 3, 9 UNION ALLSELECT 5, 25 UNION ALLSELECT k, CAST(k AS BIGINT) * CAST(k AS BIGINT)FROM (SELECT kFROM (SELECT 4 * a.Seq2 + b.Seq2 AS kFROM #Sequence AS aCROSS JOIN #Sequence AS b) AS cWHERE k <= @MaxPrimeAND k % 12 IN (1, 5)UNION ALLSELECT kFROM (SELECT 3 * a.Seq2 + b.Seq2 AS kFROM #Sequence AS aCROSS JOIN #Sequence AS b) AS cWHERE k <= @MaxPrimeAND k % 12 = 7UNION ALLSELECT kFROM (SELECT 3 * a.Seq2 - b.Seq2 AS kFROM #Sequence AS aINNER JOIN #Sequence AS b ON b.Seq < a.Seq) AS cWHERE k <= @MaxPrimeAND k % 12 = 11) AS dWHERE k % 10 IN (1, 3, 7, 9)GROUP BY kHAVING COUNT(k) IN (1, 3)--ORDER BY kCREATE UNIQUE CLUSTERED INDEX IX_Primes ON #Primes (Prime2, Prime)SELECT p.PrimeFROM #Primes AS pWHERE NOT EXISTS (SELECT 1FROM #Primes AS xWHERE x.Prime2 <= p.PrimeAND p.Prime % x.Prime = 0)AND p.Prime <= @MaxPrimeDROP TABLE #Primes, #Sequence`