Nth Prime Number - SQL Server Forums

Please start any new threads on our new site at https://forums.sqlteam.com. We've got lots of great SQL Server experts to answer whatever question you can come up with.

All Forums

General SQL Server Forums

Script Library

Nth Prime Number

Author

Topic

RyanRandall
Master Smack Fu Yak Hacker

1074 Posts

Posted - 2006-07-27 : 11:18:29

This function returns the nth prime...

create function dbo.F_NTH_PRIME(@n bigint) returns bigint as
begin
    declare @MaxNumber bigint, @i bigint
    set @MaxNumber = case when @n <=6 then 20 else @n * log(@n) + @n * log(log(@n)) end

    declare @t table (n bigint identity(1, 1), i bigint)
    insert @t select i from dbo.F_TABLE_PRIME(@MaxNumber)
    select @i = i from @t where n = @n

    return @i
end

--calculation (ran in 2 seconds for me)
select n, dbo.F_NTH_PRIME(n) as 'nth prime' from (
    select 1 n union select 2 union select 3 union select 10 union
    select 25 union select 100 union select 1000 union select 9593 union select 10000) a

/*results
n           nth prime            
----------- -------------------- 
1           2
2           3
3           5
10          29
25          97
100         541
1000        7919
9593        100003
10000       104729
*/

For dbo.F_TABLE_PRIME, see http://www.sqlteam.com/forums/topic.asp?TOPIC_ID=69646

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

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

SwePeso
Patron Saint of Lost Yaks

30421 Posts

Posted - 2006-08-01 : 08:07:43

Interested in prime number factorization?
This function returns all prime number factors for a given number

This function was previously posted under a different topic

CREATE FUNCTION	dbo.fnGetPrimeFactors
(
	@Number INT
)
RETURNS @Primes TABLE
	(
		Prime INT
	)
AS

BEGIN
	IF @Number < 2
		RETURN

	WHILE @Number % 2 = 0
		BEGIN
			INSERT	@Primes
			SELECT	2

			SELECT	@Number = @Number / 2
		END

	DECLARE	@PseudoPrimes BIGINT,
		@PseudoPrime BIGINT

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

	WHILE @PseudoPrime <= @PseudoPrimes
		IF (@Number - 2 * @PseudoPrime * @PseudoPrime - 2 * @PseudoPrime) % (2 * @PseudoPrime + 1) = 0
			BEGIN
				INSERT	@Primes
				SELECT	2 * @PseudoPrime + 1

				SELECT	@Number = (2 * @Number + 1) / (2 * @PseudoPrime + 1),
					@PseudoPrime = 1,
					@PseudoPrimes = (SQRT(@Number) - 1) / 2,
					@Number = (@Number - 1) / 2
			END
		ELSE
			SELECT	@PseudoPrime = @PseudoPrime + 1

	IF @Number > 0
		INSERT	@Primes
		SELECT	2 * @Number + 1

	RETURN
END

Peter Larsson
Helsingborg, Sweden

Subscribe to SQLTeam.com

SQLTeam.com Articles via RSS

SQLTeam.com Weblog via RSS

- Advertisement -

Resources