quote:

---

Originally posted by Michael Valentine Jones

It should be faster to use the Sieve of Eratosthenes algorithm.
http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

Basically, you only need to check up to the square root of the candidate prime, because if a number has a factor, at least one will be less than or equal to the square root.



CODO ERGO SUM

---

delete @t where i >= (@i * @i) and i % @i = 0

declare @T_PRIME table (PRIME int primary key clustered )

declare @start datetime
select @start = getdate()
insert into @T_PRIME
select i 
from dbo.F_TABLE_PRIME(1000000) order by i


select [Elapsed time]=right(convert(varchar(24),getdate()-@start,121),12)

select	
	[Prime Count] = count(*),
	[Last Prime] = max(PRIME)
from @T_PRIME

(78498 row(s) affected)

Elapsed time 
------------ 
00:00:47.267

(1 row(s) affected)

Prime Count Last Prime  
----------- ----------- 
78498       999983

(1 row(s) affected)

set nocount on
declare @num int
declare @limit int
declare @cnt int
declare @sqrt int
declare @rm60 int
declare @start datetime
declare @T_PRIME table (PRIME int primary key clustered )
insert into @T_PRIME (prime) select 2

set @num = 1
set @limit = 1000000
--set @limit = 16000000
set @cnt = 0
select @start = getdate()

while @num <  @limit
	begin
	set @num = @num+2

	-- Partial implementation Sieve of Atkin
	if @num > 199
	if
	(@num%2=0) or (@num%3=0) or (@num%5=0) or (@num%7=0) or
	(@num%11=0) or (@num%13=0) or (@num%17=0) or (@num%19=0) or
	(@num%23=0) or (@num%29=0) or (@num%31=0) or (@num%37=0) or
	(@num%41=0) or (@num%43=0) or (@num%47=0) or (@num%53=0) or
	(@num%59=0) or (@num%61=0) or (@num%67=0) or (@num%71=0) or
	(@num%73=0) or (@num%79=0) or (@num%83=0) or (@num%89=0) or
	(@num%97=0) or (@num%101=0) or (@num%103=0) or (@num%107=0) or
	(@num%109=0) or (@num%113=0) or (@num%127=0) or (@num%131=0) or 
	(@num%137=0) or (@num%139=0) or (@num%149=0) or (@num%151=0) or
	(@num%157=0) or (@num%163=0) or (@num%167=0) or (@num%173=0) or
	(@num%179=0) or (@num%181=0) or (@num%191=0) or (@num%193=0) or
	(@num%197=0) or (@num%199=0)
	continue

	set @sqrt = floor(sqrt(@num))

	insert into @T_PRIME (prime)
	select @num
	where
		not exists (
		select
			*
		from @T_PRIME a
		where
			PRIME <= @sqrt and
			@num%a.PRIME = 0
		)

	set @cnt = @cnt+1
	end -- end while

select [Elapsed time]=right(convert(varchar(24),getdate()-@start,121),12)

select	[Limit] = @limit, 
	[table scan count] = @cnt,
	[Prime Count] = count(*),
	[Last Prime] = max(PRIME)
from @T_PRIME

select [Last Prime] =max(PRIME)
from (select top 1000000 * from @T_PRIME order by PRIME ) A

Elapsed time 
------------ 
00:00:30.953

Limit       table scan count Prime Count Last Prime  
----------- ---------------- ----------- ----------- 
1000000     102851           78498       999983

Last Prime  
----------- 
999983

Elapsed time 
------------ 
00:02:58.057

Limit       table scan count Prime Count Last Prime  
----------- ---------------- ----------- ----------- 
5000000     521833           348513      4999999

Last Prime  
----------- 
4999999

(348513 row(s) affected)

Elapsed time 
------------ 
00:08:50.043

(1 row(s) affected)

Prime Count Last Prime  
----------- ----------- 
348513      4999999

(1 row(s) affected)

quote:

---

Originally posted by RyanRandall

Nice work, Michael. Thanks

Where did Peso's post go? Peso?


Ryan Randall
www.monsoonmalabar.com London-based IT consultancy

Solutions are easy. Understanding the problem, now, that's the hard part.

---

quote:

---

Originally posted by Michael Valentine Jones

I wonder how much of the runtime of the F_TABLE_PRIME function is due to the overhead of running the F_TABLE_NUMBER_RANGE function? Have you looked at that?



CODO ERGO SUM

---

a) select 2 union all select 3 union all
b) having count(k) in (1, 3)
c) set @i = 5
d) select * from @t

a) select 2 union all select 3 union all select 5 union all
b) having count(k) in (1, 3) and k % 10 in (1,3,7,9)
c) set @i = 7
d) select * from @t where i <= @maxnumber

quote:

---

Originally posted by RyanRandall

quote:

---

Originally posted by Michael Valentine Jones

I wonder how much of the runtime of the F_TABLE_PRIME function is due to the overhead of running the F_TABLE_NUMBER_RANGE function? Have you looked at that?



CODO ERGO SUM

---

Yeah, it's pretty insignificant because we're only using F_TABLE_NUMBER_RANGE to generate numbers to @SqrtMaxNumber (so for @MaxNumber = 1,000,000 it only generates numbers 1-1,000), and as you know F_TABLE_NUMBER_RANGE is like lightning for that kind of range.


Ryan Randall
www.monsoonmalabar.com London-based IT consultancy

Solutions are easy. Understanding the problem, now, that's the hard part.

---

quote:

---

Originally posted by Peso

Changing

a) select 2 union all select 3 union all
b) having count(k) in (1, 3)
c) set @i = 5
d) select * from @t

to

a) select 2 union all select 3 union all select 5 union all
b) having count(k) in (1, 3) and k % 10 in (1,3,7,9)
c) set @i = 7
d) select * from @t where i <= @maxnumber

slashed 10% of the time for me...

Peter Larsson
Helsingborg, Sweden

---

quote:

---

So to find all the prime numbers up to 1,000,000, do you still pass a value of @MaxNumber = 1,000,000?

---

CREATE FUNCTION	dbo.fnIsPrime
(
	@Number INT
)
RETURNS BIT
AS

BEGIN
	IF @Number < 2
		RETURN 0

	IF @Number % 10 IN (0, 2, 4, 5, 6, 8)
		RETURN CASE WHEN @Number IN (2, 5) THEN 1 ELSE 0 END

	DECLARE	@PseudoPrimes BIGINT,
		@PseudoPrime BIGINT,
		@IsPrime BIT

	SELECT	@PseudoPrime = 1,
		@PseudoPrimes = (SQRT(@Number) - 1) / 2,
		@IsPrime = 1,
		@Number = (@Number - 1) / 2

	WHILE @PseudoPrime <= @PseudoPrimes
		IF (@Number - 2 * @PseudoPrime * @PseudoPrime - 2 * @PseudoPrime) % (2 * @PseudoPrime + 1) = 0
			BEGIN
				SELECT	@IsPrime = 0
				BREAK
			END
		ELSE
			SELECT	@PseudoPrime = @PseudoPrime + 1

	RETURN	@IsPrime
END

/* DROP TABLE dbo.TallyPrime
CREATE TABLE	dbo.TallyPrime
		(
			Number BIGINT PRIMARY KEY CLUSTERED,
			a BIGINT NOT NULL,
			b BIGINT NOT NULL,
			p1 BIGINT NOT NULL,
			p2 BIGINT NOT NULL,
			n1 BIGINT NOT NULL,
			n2 BIGINT NOT NULL,
			y1 BIGINT NOT NULL,
			y2 BIGINT NOT NULL
		)

INSERT		dbo.TallyPrime
		(
			Number,
			a,
			b,
			p1,
			p2,
			n1,
			n2,
			y1,
			y2
		)
SELECT		Number,
		2 * Number * Number + 2 * Number AS a,
		2 * Number + 1 AS b,
		(SQRT(6 * Number - 1) - 1) / 2 AS p1,
		(SQRT(6 * Number + 1) - 1) / 2 AS p2,
		6 * Number - 1 AS n1,
		6 * Number + 1 AS n2,
		3 * Number - 1 AS y1,
		3 * Number AS y2
FROM		(
			SELECT		TOP(2000000)
					CAST(2048 * v1.Number + v2.Number AS BIGINT) AS Number
			FROM		master..spt_values AS v1
			INNER JOIN	master..spt_values AS v2 ON v2.Type = 'P'
			WHERE		v1.Type = 'P'
					AND 2048 * v1.Number + v2.Number >= 1
			ORDER BY	2048 * v1.Number + v2.Number
		) AS d
ORDER BY	Number
*/
DECLARE	@MaxPrime INT

SET	@MaxPrime = 10000

SELECT	2 AS Prime UNION ALL
SELECT	3 UNION ALL

SELECT	d.Number
FROM	(
		SELECT	n1 AS Number,
			y1 AS Yak,
			p1 AS Peso
		FROM	TallyPrime
		WHERE	Number <= FLOOR((@MaxPrime + 1) / 6.0)

		UNION ALL

		SELECT	n2 AS Number,
			y2 AS Yak,
			p2 AS Peso
		FROM	TallyPrime
		WHERE	Number <= FLOOR((@MaxPrime - 1) / 6.0)
	) AS d
WHERE	NOT EXISTS	(
				SELECT	*
				FROM	TallyPrime AS e
				WHERE	e.Number <= d.Peso
					AND (d.Yak - e.a) % e.b = 0
			)

--SieveOfBlindman
--7/28/2009
--------------------------------------------------------------------------------
--This script returns all the prime numbers between 0 and 1000.
--It is based on a new algorithm which leverages the fact that all these prime
--numbers have already been calculated God-knows how many bazillion times, so
--why bother calculating them again?
--I believe this is the fastest know algorithm for returning prime numbers
--less than 1000.  The algorithm could easily be extended to larger prime
--numbers as well, but I will leave it to others to work out the details.
--------------------------------------------------------------------------------
select 2 union select 3 union select 5 union select 7 union select 11
union select 13 union select 17 union select 19 union select 23 union select 29
union select 31 union select 37 union select 41 union select 43 union select 47
union select 53 union select 59 union select 61 union select 67 union select 71
union select 73 union select 79 union select 83 union select 89 union select 97
union select 101 union select 103 union select 107 union select 109 union select 113
union select 127 union select 131 union select 137 union select 139 union select 149
union select 151 union select 157 union select 163 union select 167 union select 173
union select 179 union select 181 union select 191 union select 193 union select 197
union select 199 union select 211 union select 223 union select 227 union select 229
union select 233 union select 239 union select 241 union select 251 union select 257
union select 263 union select 269 union select 271 union select 277 union select 281
union select 283 union select 293 union select 307 union select 311 union select 313
union select 317 union select 331 union select 337 union select 347 union select 349
union select 353 union select 359 union select 367 union select 373 union select 379
union select 383 union select 389 union select 397 union select 401 union select 409
union select 419 union select 421 union select 431 union select 433 union select 439
union select 443 union select 449 union select 457 union select 461 union select 463
union select 467 union select 479 union select 487 union select 491 union select 499
union select 503 union select 509 union select 521 union select 523 union select 541
union select 547 union select 557 union select 563 union select 569 union select 571
union select 577 union select 587 union select 593 union select 599 union select 601
union select 607 union select 613 union select 617 union select 619 union select 631
union select 641 union select 643 union select 647 union select 653 union select 659
union select 661 union select 673 union select 677 union select 683 union select 691
union select 701 union select 709 union select 719 union select 727 union select 733
union select 739 union select 743 union select 751 union select 757 union select 761
union select 769 union select 773 union select 787 union select 797 union select 809
union select 811 union select 821 union select 823 union select 827 union select 829
union select 839 union select 853 union select 857 union select 859 union select 863
union select 877 union select 881 union select 883 union select 887 union select 907
union select 911 union select 919 union select 929 union select 937 union select 941
union select 947 union select 953 union select 967 union select 971 union select 977
union select 983 union select 991 union select 997

CREATE TABLE	#Numbers
		(
			Prime INT NOT NULL,
			Number BIGINT PRIMARY KEY CLUSTERED
		);

DECLARE	@Max INT;

SET	@Max = 1000000;

WITH		n0 AS (SELECT 1 AS p UNION ALL SELECT 1),
		n1 AS (SELECT 1 AS p FROM n0 AS a CROSS JOIN n0 AS b),
		n2 AS (SELECT 1 AS p FROM n1 AS a CROSS JOIN n1 AS b),
		n3 AS (SELECT 1 AS p FROM n2 AS a CROSS JOIN n2 AS b),
		n4 AS (SELECT 1 AS p FROM n3 AS a CROSS JOIN n3 AS b),
		n5 AS (SELECT 1 AS p FROM n4 AS a CROSS JOIN n4 AS b)
INSERT		#Numbers
		(
			Prime,
			Number
		)
SELECT		f.Prime,
		f.Prime * f.Prime AS Number
FROM		(
			SELECT	TOP (1 + @Max / 6)
				ROW_NUMBER() OVER (ORDER BY p)
			FROM    n5
		) AS v(Value)
CROSS APPLY	(
			VALUES	(6 * v.Value - 1),
				(6 * v.Value + 1)
		) AS f(Prime)
WHERE		f.Prime <= @Max;

SELECT	Prime
FROM	(
		VALUES	(2),
			(3)
	) AS v(Prime)
WHERE	Prime <= @Max

UNION ALL

SELECT	n.Prime
FROM	#Numbers AS n
WHERE	NOT EXISTS	(
				SELECT	*
				FROM	#Numbers AS p
				WHERE	p.Number <= n.Prime
					AND n.Prime % p.Prime = 0
			)

DROP TABLE	#Numbers;