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