

SSCEnthusiastic
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 mathcentric limiter of b.N <= a.N/2  but that extra calculation apparently cost more in the execution plan.




SSCEnthusiastic
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




SSCrazy
Group: General Forum Members
Last Login: Tuesday, December 16, 2014 9:58 AM
Points: 2,280,
Visits: 3,069


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




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




SSCEnthusiastic
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. :)




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




Grasshopper
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 nonprimes delete p from Primes p where p.p in (  get numbers that are nonprimes select s1.seq from Sequence s1 where exists (  see if s1.seq is evenly divisible by a lower number (nonprimes) 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 (nonprimes) 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




SSCommitted
Group: General Forum Members
Last Login: Tuesday, December 16, 2014 8:50 PM
Points: 1,688,
Visits: 2,271


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 TSQL, 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 64bit with SQL 2005 Developer Edition (SP2) 64bit, on an Intel QuadCore 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




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




Forum Newbie
Group: General Forum Members
Last Login: Yesterday @ 8:08 AM
Points: 3,
Visits: 303


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



