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

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.

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.

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]

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);

<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

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

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

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

Hugo is co-founder and R&D lead of perFact BV, a Dutch company that strives to improve analysis methods and to develop computer-aided tools that will generate completely functional applications from the analysis deliverable. The chosen platform for this development is SQL Server. In his spare time, Hugo likes to visit the SQL Server newsgroups, in order to share and enhance his knowledge of SQL Server.

## Comments

## Denis The SQL Menace said:

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

## Ward Pond said:

## Path Enumeration using Prime number products said:

## 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?

## Hugo Kornelis said:

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>.

## 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.

## 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.

## 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

## 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]

## 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)

;

## 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

## 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

## primenumbers said:

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

## 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.