Click here to monitor SSC
SQLServerCentral is supported by Red Gate Software Ltd.
 
Log in  ::  Register  ::  Not logged in
 
 
 
        
Home       Members    Calendar    Who's On


Add to briefcase ««12345»»»

Celko's Summer SQL Stumpers: Prime numbers Expand / Collapse
Author
Message
Posted Monday, July 27, 2009 8:26 AM
SSC-Enthusiastic

SSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-Enthusiastic

Group: General Forum Members
Last Login: Thursday, July 22, 2010 8:59 AM
Points: 110, Visits: 952
select a.N
from
(select top 1000 * from sequence) a
,(select top 1000 * from sequence) b
where
a.N % b.N = 0
and
a.N > b.N
group by
a.N
having
count(*) = 1

explain: since prime numbers only have factors 1 and themselves, find those numbers that have only 1 group of factors. The condition of 'a.N mod b.N = 0' means b.N is a factor of a.N. The condition 'a.N > b.N' prevents counting a.N = b.N as a factor as well as limiting the rows to be examined in the cross product. I tried the more math-centric limiter of b.N <= a.N/2 - but that extra calculation apparently cost more in the execution plan.
Post #760109
Posted Monday, July 27, 2009 10:05 AM
SSC-Enthusiastic

SSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-Enthusiastic

Group: General Forum Members
Last Login: Monday, November 11, 2013 2:42 AM
Points: 150, Visits: 245

Also note that 1 is not a prime number, by definition.


Actually, the reason is 'convention' not definition: certain other algorithms that depend on prime numbers mostly work better if 1 is declared not prime, but this is certainly not by definition: there is no other number that divides 1 and gives an integer. Any technical arguments that it is Prime, apply equally well to both 2 and 3, both of which are always regarded as Prime.


Throw away your pocket calculators; visit www.calcResult.com

Post #760210
Posted Monday, July 27, 2009 11:02 AM
SSCrazy

SSCrazySSCrazySSCrazySSCrazySSCrazySSCrazySSCrazySSCrazy

Group: General Forum Members
Last Login: Thursday, September 11, 2014 1:41 PM
Points: 2,278, Visits: 3,058
I think the best solution here is to use not exists. A prime number is a that is greater than 1 and only divisible by itself. Knowing this information, we can exclude all even numbers, with the exception of 2 and. This leaves us with odd numbers greater than 1. To find odd numbers that are prime, we take the current odd number and take the modulo of all the numbers less than the current odd number. If the modulo of the current odd number and the less number is equal to 0, we know that that odd value is divisible by something other than 1, so it is not a prime number.

--insert prime numbers into Primes
INSERT INTO [dbo].[Primes](p)
SELECT s1.seq AS PrimeNumbers
FROM [dbo].[Sequence] s1
WHERE
(s1.seq > 1 AND s1.seq < 10000)
AND (s1.seq % 2 = 1 or s1.seq=2)
AND NOT EXISTS(
SELECT 1
FROM [dbo].[Sequence] s2
WHERE
(s2.seq < s1.seq AND s2.seq > 1)
AND s1.seq % s2.seq = 0
)


I dont know if it is valid to do within the scope of this challendge, but I believe the best solution here would be to create a PrimeCandidate column in the sequence table. The PrimeCandidate columns would only contain valid candidates to be Prime, which includes odd numbers and the number 2. This cuts down on wasted processing and will really speed this query up.




My blog: http://jahaines.blogspot.com
Post #760243
Posted Monday, July 27, 2009 11:04 AM
Grasshopper

GrasshopperGrasshopperGrasshopperGrasshopperGrasshopperGrasshopperGrasshopperGrasshopper

Group: General Forum Members
Last Login: Thursday, March 11, 2010 1:32 PM
Points: 13, Visits: 12
Ok, maybe I am oversimplifying this; but here is my solution to derive a set of prime numbers up to 1000.

Since a prime only has 2 divisors and those divisors must be less than the number in question, lets just join the table to itself via a modulo test and count all the results that are evenly divisible.

create table #Numbers (p int)

-- Load #Numbers up with 1,000 records having p = 1 to 1,000
declare @x int
select @x = 0
while @x < 1000
begin
select @x = @x + 1
insert into #Numbers select @x
end

-- List all numbers with only 2 evenly divisible numbers

select a.p from #Numbers a, #Numbers b
where a.p % b.p = 0 and a.p <= b.p
group by a.p having count(b.p) = 2


Tweak to check only divisors less than itself; primses 10,000 and less now takes 48 seconds. Although since a these are static numbers, I do not know why the issue of time is a factor, since once calculated they can be written to a table. It seems the shortest way to derive the numbers is the most desirable... my 3 lines of code (to generate primes) seems the shortest code thus far

Post #760244
Posted Monday, July 27, 2009 11:17 AM
SSC-Enthusiastic

SSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-Enthusiastic

Group: General Forum Members
Last Login: Thursday, July 22, 2010 8:59 AM
Points: 110, Visits: 952
/*
select top 100000
[N] = identity(int,1,1)
into
#seq
from
dbo.syscolumns a
,dbo.syscolumns b
,dbo.syscolumns c
CREATE INDEX IX_N ON #seq ([N]);
*/
with prime([N])
as (
select a.[N]
from
(select top 1000 [N] from #seq) a
,(select top 1000 [N] from #seq) b
where
a.N % b.N = 0
and
a.N > b.N
group by
a.N
having
count(*) = 1
)
select count(*) from (
select [N] from prime
union all
select
a.[N]
from
#seq a
left join
prime p
on a.[N] % p.N = 0
where
a.[N] <> 1
and
a.[N] < (select power(max([N]),2) from prime)
and
p.[N] is null
) dt1

explain:
use the first method I posted to get a list of primes less than 1000 and use that to more efficiently find the primes between 1000 and 100000. Return the list of primes and those numbers which do not have as factors any number in the list. The number 1 is removed because it's not prime, only consider numbers less than the square of this highest prime in the list (else the sieve is incomplete), and return only those numbers that have no factors in the prime list.

notes:
I noticed I was starting to suffer performance issues returning a list I wasn't reading anyway, so I compared the count returned with http://primes.utm.edu/howmany.shtml
I also tried using a sequence table to 10 million rows. I figured I'd need to use the top 3200 rows from the sequence table to make the primes list (which I successfully ran to as much as 5000) but I don't have the patience to wait for the server to find the 664,579 rows. As it stands now, it's returning the 9592 count from N<= 100,000 rows in 6 seconds.
I would love to spend more time on this, but I have to get back to work. :)
Post #760250
Posted Monday, July 27, 2009 11:44 AM
Ten Centuries

Ten CenturiesTen CenturiesTen CenturiesTen CenturiesTen CenturiesTen CenturiesTen CenturiesTen Centuries

Group: General Forum Members
Last Login: Thursday, January 9, 2014 4:10 PM
Points: 1,388, Visits: 239
Not sure if this has been posted yet, but here is my take...

Code could be compacted a bit and temp tables would be a bit more efficient for larger limits...


DECLARE @Primes TABLE(p INT NOT NULL)
DECLARE @Sequence TABLE(seq INT NOT NULL)
DECLARE @Digits TABLE(i INT NOT NULL)
DECLARE @RemoveTable TABLE(i INT)

DECLARE @limit INT; SET @limit = 1000

--load up digits per provided filling mechanism
INSERT INTO @Digits VALUES(1)
INSERT INTO @Digits VALUES(2)
INSERT INTO @Digits VALUES(3)
INSERT INTO @Digits VALUES(4)
INSERT INTO @Digits VALUES(5)
INSERT INTO @Digits VALUES(6)
INSERT INTO @Digits VALUES(7)
INSERT INTO @Digits VALUES(8)
INSERT INTO @Digits VALUES(9)
INSERT INTO @Digits VALUES(0)

--add to sequence table per provided filling mechanism
INSERT INTO @Sequence
SELECT (D3.i * 1000 + D2.i * 100 + D1.i * 10 + D0.i + 1) AS seq
FROM @Digits AS D0, @Digits AS D1, @Digits AS D2, @Digits AS D3

--add non prime numbers to remove table. This uses a cartesian join, restricting on:
-- 1. joining on matching values
-- 2. joined table value less than left table value
-- 3. values less than pre-defined limit and greater than or equal to zero
-- 4. left table mod right table = 0
--
--Distinct values are returned

INSERT INTO @RemoveTable
SELECT DISTINCT S1.seq
FROM @Sequence S1, @Sequence S2
WHERE S1.seq <> S2.seq
AND S2.seq < s1.[seq]
AND S1.seq BETWEEN 2 AND @limit
AND S2.seq BETWEEN 2 AND @limit - 1
AND S1.seq % S2.seq = 0


SELECT seq FROM @Sequence
WHERE seq BETWEEN 2 AND @limit
AND seq NOT IN
(
SELECT i FROM @RemoveTable
)
ORDER BY seq



Post #760262
Posted Monday, July 27, 2009 12:04 PM
Grasshopper

GrasshopperGrasshopperGrasshopperGrasshopperGrasshopperGrasshopperGrasshopperGrasshopper

Group: General Forum Members
Last Login: Wednesday, June 1, 2011 8:25 AM
Points: 15, Visits: 52
----------------
-- solution #1
----------------

--clear primes table
delete from Primes

-- add all numbers
insert into Primes (p)
select seq
from Sequence
where seq > 1

-- delete non-primes
delete p
from Primes p
where p.p in (
-- get numbers that are non-primes
select s1.seq
from Sequence s1
where exists (
-- see if s1.seq is evenly divisible by a lower number (non-primes)
select *
from Sequence s2
where s2.seq between 2 and (s1.seq / 2)
and s1.seq % s2.seq = 0
)
)

-- return primes
select p
from Primes p
order by p.p

----------------
-- solution #2
----------------

--clear primes table
delete from Primes

-- insert primes
insert into Primes (p)
select s1.seq
from Sequence s1
where s1.seq > 1 -- prime must be > 1
and not exists (
-- get numbers that are evenly divisible by a lower number (non-primes)
select *
from Sequence s2
where s2.seq between 2 and (s1.seq / 2)
and s1.seq % s2.seq = 0
)

-- return primes
select p
from Primes p
order by p.p

Post #760273
Posted Monday, July 27, 2009 3:06 PM
SSCommitted

SSCommittedSSCommittedSSCommittedSSCommittedSSCommittedSSCommittedSSCommittedSSCommitted

Group: General Forum Members
Last Login: Monday, September 8, 2014 4:07 PM
Points: 1,669, Visits: 2,215
Hmmm... seeing some interesting approaches. I'm going to go with a fairly simple combination of techniques that doesn't end up with scaling problems, as many of these solutions appear to have. I tried answer #3 in the original article, and nothing I did was able to get it to produce correct results much above 6500. One thing I decided early on would be necessary is to know exactly how many prime numbers there are for a given largest number in your sequence table. I went to wolframalpha.com and asked it "how many prime numbers are < 10000000" (that's my high number in my "tally table" (see Jeff Moden's post on creating on of those)).

The answers to that question and the other multiples of 10 are:

10,000,000 - 664,579
1,000,000 - 78,498
100,000 - 9,592
10,000 - 1,229

Anyway, here's my code, which uses table variables to hold the PRIMES and the candidates (NUMS), and limits the candidates to numbers 7 and higher that end in 1, 3, 7, or 9, and are of the form 6 * N + or - 1, which I found on WikiPedia. Translated into T-SQL, that last piece is N % 6 IN (1, 5).

I then UNION ALL the early primes (2,3,5) with candidates that don't have any factors up to the ceiling of the square root, which was generated with the creation of the candidates (NUMS) table. My run time on Vista Ultimate 64-bit with SQL 2005 Developer Edition (SP2) 64-bit, on an Intel Quad-Core Q9550 at 2.83 GHz, has consistently been in the 3 mins 36 secs to 3 mins 48 secs timeframe, and produces all 664,579 primes. The most recent run was 3 mins 38.073 secs.

DECLARE @START AS DATETIME, @END AS DATETIME
SET @START = GETDATE()

DECLARE @PRIMES TABLE (
PRIME INT NOT NULL PRIMARY KEY CLUSTERED
)
DECLARE @NUMS TABLE (
N INT NOT NULL PRIMARY KEY CLUSTERED,
CN AS (RIGHT(CAST(N AS varchar(10)),1)) PERSISTED,
SR AS CAST(CEILING(SQRT(N)) AS INT) PERSISTED
)
INSERT INTO @NUMS(N)
SELECT N
FROM master.dbo.Tally
WHERE N > 6 AND
RIGHT(CAST(N AS varchar(10)),1) IN ('1','3','7','9') AND
N % 6 IN (1, 5)

INSERT INTO @PRIMES(PRIME)
SELECT CAST(2 AS INT) AS PRIME
UNION ALL
SELECT CAST(3 AS INT)
UNION ALL
SELECT CAST(5 AS INT)
UNION ALL
SELECT N1.N
FROM @NUMS AS N1
WHERE NOT EXISTS ( SELECT 1 FROM master.dbo.Tally AS N2 WHERE N2.N > 1 AND N2.N <= N1.SR AND N1.N % N2.N = 0 )

SELECT *
FROM @PRIMES

SET @END = GETDATE()
PRINT 'Total Duration: ' + CAST(CAST(DATEDIFF(ms, @START, @END)/1000. AS decimal(7,3)) AS varchar(15)) + ' seconds'

I added some small code to print out the duration in seconds. I don't recall if SQL Server 2000 was able to use calculated fields or not, but that could be easily overcome by just moving that code around. My original code didn't use calculated fields, but it didn't run any faster or slower, so I'm not sure it made or makes, any difference.

Steve
(aka smunson)


Steve
(aka sgmunson)

Internet ATM Machine
Post #760383
Posted Monday, July 27, 2009 3:21 PM
SSC Rookie

SSC RookieSSC RookieSSC RookieSSC RookieSSC RookieSSC RookieSSC RookieSSC Rookie

Group: General Forum Members
Last Login: Friday, November 6, 2009 11:29 AM
Points: 26, Visits: 126
Assuming that I can start with a table for factors with 2 and 3.
Using the maximum prime number on the current factors table, a upper limit is determined for finding a prime number.
If this upper limit is insufficient, a loop adds as many prime numbers to the table as possible with the current list of factors.
Once we have a factor greater than the square root of the target limit, we can add all of the remaining prime numbers less than the target limit in one statement.

The prime numbers are determined using a combination of the number theory (6x plus or minus 1) and modulo operations for all known primes less than the target limit.

DECLARE @MAXLIMIT int DECLARE @LIMIT int
SET @LIMIT = 1000
/* What is the biggest prime number we can find from the current factors table*/
SELECT @MAXLIMIT = MAX(f) * MAX(f)
FROM Factors
/* If we need bigger factors, add prime numbers up to the square of our current largest factor*/
WHILE @MAXLIMIT < @LIMIT
BEGIN
INSERT
INTO Factors(f)
SELECT 6 * Sequence.seq + S.S AS f
FROM Sequence CROSS JOIN
(SELECT S FROM Switch) AS S
WHERE (6 * Sequence.seq + 1 <= @MAXLIMIT)
AND (0 NOT IN (SELECT (6 * Sequence.seq + S.S) % f AS FactorialTest
FROM Factors))
/* What is the biggest prime number we can find from the current factors table*/
SELECT @MAXLIMIT = MAX(f) * MAX(f)
FROM Factors
END

/* Insert the factors table into Primes and add the remaining primes less than @Limit*/
INSERT
INTO Primes(p)
SELECT F FROM Factors
UNION
SELECT 6 * Sequence.seq + S.S AS f
FROM Sequence CROSS JOIN
(SELECT S FROM Switch) AS S
WHERE (6 * Sequence.seq + 1 <= @LIMIT)
AND (0 NOT IN (SELECT (6 * Sequence.seq + S.S) % f AS FactorialTest
FROM Factors))



This checks only the candidates from number theory against a small set known primes. Ideally, the factors table would only contain prime numbers up to the square root of the target limit. The way that I build the table will add more factors than are actually needed, but it was the best I could come up with to solve for any generic target limit.

Tom

Post #760387
Posted Monday, July 27, 2009 3:57 PM
Forum Newbie

Forum NewbieForum NewbieForum NewbieForum NewbieForum NewbieForum NewbieForum NewbieForum Newbie

Group: General Forum Members
Last Login: Tuesday, July 15, 2014 3:00 PM
Points: 3, Visits: 299
Looks like I was beaten to the methodology, but this is what I jotted down this morning. It doesn't work on SQL2000 or less, but hey--I don't either! I assume a numbers table already exists in the following form:

CREATE TABLE [tbl_Numbers] ( 
Number int NOT NULL CONSTRAINT pkNumbers_Number_UC PRIMARY KEY CLUSTERED (Number)
)
GO

and is populated with 1000 entries.
SELECT
*
FROM
tbl_Numbers
EXCEPT
SELECT
candidate.Number
FROM
tbl_Numbers AS candidate
CROSS JOIN tbl_Numbers AS factor
WHERE
factor.Number < candidate.Number
AND factor.Number > 1
AND candidate.Number % factor.Number = 0

This completes in about 49 milliseconds on my home system.
Post #760396
« Prev Topic | Next Topic »

Add to briefcase ««12345»»»

Permissions Expand / Collapse