Recent PostsRecent Posts Popular TopicsPopular Topics
 Home Search Members Calendar Who's On

 Celko's Summer SQL Stumpers: Prime numbers Rate Topic Display Mode Topic Options
Author
 Message
 Posted Monday, July 27, 2009 8:26 AM
 SSC-Enthusiastic Group: General Forum Members Last Login: Thursday, July 22, 2010 8:59 AM Points: 110, Visits: 952
 select a.Nfrom (select top 1000 * from sequence) a ,(select top 1000 * from sequence) bwhere a.N % b.N = 0 and a.N > b.Ngroup by a.Nhaving count(*) = 1explain: 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 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 Group: General Forum Members Last Login: Monday, March 23, 2015 4:19 PM Points: 2,280, Visits: 3,076
 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 PrimesINSERT INTO [dbo].[Primes](p)SELECT s1.seq AS PrimeNumbersFROM [dbo].[Sequence] s1WHERE (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 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,000declare @x intselect @x = 0while @x < 1000begin select @x = @x + 1 insert into #Numbers select @xend-- List all numbers with only 2 evenly divisible numbersselect a.p from #Numbers a, #Numbers b where a.p % b.p = 0 and a.p <= b.pgroup by a.p having count(b.p) = 2Tweak 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 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 #seqfrom dbo.syscolumns a ,dbo.syscolumns b ,dbo.syscolumns cCREATE 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) dt1explain: 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 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 mechanismINSERT 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 mechanismINSERT INTO @SequenceSELECT (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 returnedINSERT 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 @SequenceWHERE 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 Group: General Forum Members Last Login: Wednesday, June 1, 2011 8:25 AM Points: 15, Visits: 52
 `------------------ solution #1------------------clear primes tabledelete from Primes-- add all numbersinsert into Primes (p)select seqfrom Sequencewhere seq > 1-- delete non-primesdelete pfrom Primes pwhere 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 primesselect pfrom Primes porder by p.p------------------ solution #2------------------clear primes tabledelete from Primes-- insert primesinsert into Primes (p)select s1.seqfrom Sequence s1where s1.seq > 1 -- prime must be > 1and 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 primesselect pfrom Primes porder by p.p`
Post #760273
 Posted Monday, July 27, 2009 3:06 PM
 SSCommitted Group: General Forum Members Last Login: Monday, April 20, 2015 6:15 PM Points: 1,868, Visits: 2,368
 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,5791,000,000 - 78,498100,000 - 9,59210,000 - 1,229Anyway, 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 DATETIMESET @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 NFROM master.dbo.TallyWHERE 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 @PRIMESSET @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)Helpful Investing InfoHealthy Living InfoHelpful Business Info
Post #760383
 Posted Monday, July 27, 2009 3:21 PM
 SSC 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 intSET @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 < @LIMITBEGIN 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 FactorsUNION 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 Group: General Forum Members Last Login: Wednesday, April 29, 2015 9:50 AM Points: 3, Visits: 320
 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_NumbersEXCEPTSELECT candidate.NumberFROM tbl_Numbers AS candidate CROSS JOIN tbl_Numbers AS factorWHERE 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

 Permissions