THE SQL Server Blog Spot on the Web

Welcome to SQLblog.com - The SQL Server blog spot on the web Sign in | |
 in SELECT Hints, Tips, Tricks FROM Hugo Kornelis WHERE RDBMS = 'SQL Server' (Entire Site) Search

The prime number challenge – great waste of time!

This blog has moved! You can find this content at the following new location:

https://SQLServerFast.com/blog/hugo/2006/09/the-prime-number-challenge-great-waste-of-time/

Published Saturday, September 23, 2006 10:54 PM by Hugo Kornelis

Denis The SQL Menace said:

Hugo, let me know how many seconds (yes seconds) this version takes

SET NOCOUNT ON

DECLARE @i INT

-- Create a 10-digit table
DECLARE @D TABLE (N INT)
INSERT INTO @D (N)
SELECT 0 UNION ALL
SELECT 1 UNION ALL
SELECT 2 UNION ALL
SELECT 3 UNION ALL
SELECT 4

INSERT INTO @D (N)
SELECT N+5 FROM @D

-- build a small sieve table between 2 and 1000
DECLARE @T TABLE (N INT)
INSERT INTO @T( N )
SELECT 1+A.N+10*(B.N+10*C.N)
FROM @D A, @D B, @D C

DELETE FROM @T WHERE N = 1

SET @I = 2
WHILE @I <= SQRT(1000) BEGIN     DELETE FROM @T WHERE N % @I = 0 AND N > @I
SET @I = @I + 1
END

-- Create large table between 1001 and 1000000
SELECT A+10*(B+10*(C+10*(D+10*(E+ 10*F)))) AS N
INTO #P
FROM
(    SELECT A.N AS A, B.N AS B, C.N AS C, D.N AS D, E.N AS E, F.N AS F
FROM @D A, @D B, @D C, @D D, @D E, @D F
WHERE A.N in (1, 3, 7, 9)  -- Not divisible by 2 or 5
) blah
WHERE (A+B+C+D+E+F) % 3 <> 0 -- Or 3
AND (A+3*B+2*C-D-3*E-2*F) % 7 <> 0 -- Or 7
AND (B-A+D-C+F-E) % 11 <> 0 -- Or 11
AND D|E|F <> 0 -- Don't include the first 1000 numbers,
--we already have these in the small sieve table
UNION ALL SELECT 1000000

-- sieve the big table with smaller one
SELECT @I = 2
WHILE @I IS NOT NULL
BEGIN
DELETE FROM #P WHERE N% @I = 0
SELECT @I = MIN(N) FROM @T WHERE N > @I
END

-- add primes up to 1000
INSERT INTO #P SELECT N FROM @T

-- Here are the results
--78498 rows
SELECT  * FROM #P ORDER BY 1

drop table #P
go
September 23, 2006 5:19 PM

Ward Pond said:

Six seconds on my laptop, Denis..  pretty cool!
September 23, 2006 11:02 PM

Path Enumeration using Prime number products said:

September 25, 2006 1:10 AM

Lonedog said:

WHERE (A+B+C+D+E+F) % 3 <> 0 -- Or 3
AND (A+3*B+2*C-D-3*E-2*F) % 7 <> 0 -- Or 7
AND (B-A+D-C+F-E) % 11 <> 0 -- Or 11

Is there a mathematical reference for any of the lines?
October 18, 2006 2:54 PM

Hugo Kornelis said:

Hi Lonedog,

I understand less than half of it myself, but I think that http://en.wikipedia.org/wiki/Divisibility_rule should be the reference you want.

I must admit the the (A+B+C+D+E+F) % 3 <> 0 is the only part I understand <g>.
October 23, 2006 3:36 PM

Ward Pond said:

This is the modulus operator, which returns the remainder of a division by the operand.  So, if one Denis' modulus operations returns 0, the calculated expression is evenly divisible by the operand.  This is a very performant way of finding factors.

January 22, 2007 10:40 PM

RBArryYoung said:

What he is doing is what we used to cal "digital factoring" (before that came to mean something else), wherein he is using the decimal digits of the number to calculate "digital roots" for various primes which shortcut methods for determining their remainder modulo that prime.

These are tricks that are used by mathemagicians, etc. to do various mental calculations.

February 27, 2009 12:03 AM

RBArryYoung said:

Here is what I would use.  It runs about 15-20% faster on my system than Denis's (of course, Ive had an extra three years too):

If Not (object_id('tempdb..#Sieve2') is Null)  Drop table #Sieve2

If Not (object_id('tempdb..#Sieve3') is Null)  Drop table #Sieve3

If Not (object_id('tempdb..#Candidates1M') is Null)  Drop table #Candidates1M

If Not (object_id('tempdb..#Candidates1Ma') is Null)  Drop table #Candidates1Ma

;WITH Primes7to36 as (

Select 7 as p

Union ALL Select 11

Union ALL Select 13

Union ALL Select 17

Union ALL Select 19

Union ALL Select 23

Union ALL Select 29

Union ALL Select 31)

Select p

Into #Sieve2

From Primes7to36

;WITH Base30 as (Select 1 as rem

Union Select 7 as p

Union ALL Select 11

Union ALL Select 13

Union ALL Select 17

Union ALL Select 19

Union ALL Select 23

Union ALL Select 29)

, Numbers10E4 as (Select TOP 10000

ROW_NUMBER() Over(Order by id) as Num

From master.sys.syscolumns)

, Numbers34 as (Select Top 34 Num

From Numbers10E4)

, Candidates1000 as (

SELECT rem+30*Num as Cand

From Base30

Cross Join Numbers34)

, Primes7to1000 as (

Select p From #sieve2 --Primes7to36

Where p<>7 and p<>11

UNION ALL

Select Cand as p

From Candidates1000

Where Cand <= 1000

And Not Exists(Select *

From #Sieve2

Where (Cand % p)=0))

SELECT p

Into #Sieve3

From Primes7to1000

;WITH Base30 as (Select 1 as rem

Union Select 7 as p

Union ALL Select 11

Union ALL Select 13

Union ALL Select 17

Union ALL Select 19

Union ALL Select 23

Union ALL Select 29)

, Base90 as (Select rem as rem From Base30

Union ALL Select rem+30 From Base30

Union ALL Select rem+60 From Base30)

, Numbers11120 as (Select TOP 11120

ROW_NUMBER() Over(Order by id) as Num

From master.sys.syscolumns)

, Candidates1M as (

Select rem+(90*Num) as Cand

From Base90

Cross Join Numbers11120)

, Cand2_1M as (

Select Cand

From Candidates1M

Where Cand <= 1000000

And (Cand % 7) <> 0

And (Cand % 11) <> 0

)

Select Cand

Into #Candidates1M

From Cand2_1m

;WITH Cand2a as (

Select Cand as p

From #Candidates1M

Where Cand <= 1000000

And Not Exists(Select *

From #Sieve3

Where (Cand % p)=0

)

)

Select p as Cand

Into #Candidates1Ma

From Cand2a

;WITH FilterPrimes as (

Select 2 as p

Union ALL Select 3

Union ALL Select 5

Union ALL Select 7

Union ALL Select 11

)

, PrimesLE1M as ( Select p From FilterPrimes

UNION ALL Select p From #Sieve3

UNION ALL

Select Cand as p

From #Candidates1Ma

)

Select p

From PrimesLE1M

--=======

-- RBarryYoung

February 28, 2009 12:37 AM

Stan Hudecek said:

also wish to prove my (in)sanity...takes about 0.7 sec on my notebook. (no access to real server at the moment)  trying to do it all in one sql statement as well.  seemed to run faster with a pre-populated a table of ints with an index rather then the row_number, but this seems fairly fast to me.

select 2 [num] union select 3 union select 5 union

select num

from

(

select num,min(num%den) [div]

from

(

select a.id [num], b.id [den]

from

(

select top 10000 row_number() over(order by id) [id]

from master.sys.syscolumns

--from (select top 40000 c1.id from master.sys.syscolumns c1 cross join master.sys.syscolumns c2) [c]

) [a]

join

(

select top 100 row_number() over(order by id) [id]

from master.sys.syscolumns

) [b] on (

a.id % 2 <> 0

and a.id % 3 <> 0

and a.id % 5 <> 0

and b.id > 1

and b.id <= sqrt( a.id)

)

) [base]

group by num

having min(num%den)>0

) [cols]

March 7, 2009 5:46 AM

Jeff Moden said:

Hi Hugo,

I tried your code on a million rows and it drove all 4 processors on my poor little I5 laptop into the stops.  I halted it after 10 minutes.

The only things I can think of for such a difference between what you got for performance and what I got would be number of CPUs, type of disk, and, of course, how the Numbers table you used was built.  Here's how I built that.  Please let me know what kind of box you were using and whether or not I correctly duplicated your Numbers table.  Thanks.

CREATE TABLE dbo.Numbers (Number INT PRIMARY KEY CLUSTERED);

GO

INSERT INTO dbo.Numbers WITH(TABLOCK)

(Number)

SELECT TOP 5764801

Number = ROW_NUMBER()OVER(ORDER BY (SELECT NULL))

FROM sys.all_columns ac1

CROSS JOIN sys.all_columns ac2

OPTION (RECOMPILE)

;

February 25, 2017 1:12 AM

Prime Numbers said:

<a href="www.nuclearstrategy.co.uk/prime-number-distribution-series">Prime numbers</a> are a special kind of natural numbers or positive integers which are exactly divisible by 1 and the number itself or such as 2,3,5,7 and 11.For more details visit our websites http://nuclearstrategy.co.uk/prime-number-distribution-series or feel free to call us +44(0)8453138454 or contact us generalenquiries@nuclearstrategy.co.uk

June 2, 2017 3:26 AM

Prime Numbers said:

Prime numbers are a special kind of natural numbers or positive integers which are exactly divisible by 1 and the number itself or such as 2,3,5,7 and 11.For more details visit our websites http://nuclearstrategy.co.uk/prime-number-distribution-series or feel free to call us +44(0)8453138454 or contact us generalenquiries@nuclearstrategy.co.uk

June 2, 2017 3:27 AM

What is a prime number? This definition explains what a prime number is and lists examples. See also different types of primes and links to information about prime number distribution . For more details visit our website http://nuclearstrategy.co.uk/prime-number-distribution-series

November 27, 2017 4:37 AM

Denver Goettle said:

Generally speaking, whereas this e-book might present a priceless handbook for some students, I don’t imagine its style engages the attention of the reader

and it doesn’t try to offer an intensive clarification of

linear algebra. https://math-problem-solver.com/ .

The social worker genuinely needs to know the client.

February 5, 2018 2:01 PM

(required)
(required)
Submit