# Thread: Prime factors using T-SQL

1. Resident Curmudgeon
Join Date
Feb 2004
Location
In front of the computer
Posts
15,579

## Unanswered: Prime factors using T-SQL

I had to work out a prime factors routine to solve another problem, and used T-SQL because it is what I had handy at the moment. I was surprised at how efficient it was and thought I'd throw the code sample out for others to play with and improve.
Code:
```DECLARE
@d1			DATETIME	-- Dummy var used to compute ms of runtime
,  @i			BIGINT		-- Working accumulator
,  @v			BIGINT		-- Working divisor

SET @d1 = GETDATE()			-- Store begin of run

DECLARE @t TABLE (v BIGINT)	-- Table to hold factors

SET @i = 1234567890			-- Set initial value

WHILE 0 = @i % 2			-- Factor out twos first
BEGIN
INSERT @t VALUES (2)	-- Store factor
SET @i = @i / 2		-- Reduce accumulator
END

SET @v = 3					-- Check all odd numbers

WHILE @v * @v < @i			-- While divisor less than sqr of accumulator
BEGIN
WHILE 0 = @i % @v		-- Test for even divisibility
BEGIN
INSERT @t VALUES (@v)
SET @i = @i / @v	-- Reduce accumulator
END

SET @v = 2 + @v		-- Skip to next divisor
END

INSERT @t VALUES (@i)		-- Remainder is last prime factor

SELECT DATEDIFF(ms, @d1, GetDate())	-- Computations are done

SELECT v, COUNT(*) FROM @t GROUP BY v

SET @i = 1					-- Prove our work
SELECT @i = @i * v FROM @t
SELECT @i					-- Must be initial value```
-PatP

2. Resident Curmudgeon
Join Date
Feb 2004
Location
In front of the computer
Posts
15,579
I'm kind of bummed, I'd hoped for some discussion.... This was an interesting issue for me because I normally solve this kind of problem in middleware instead of at the database, but for this particular problem that would have made the overall code execution take too long.

FWIW, I left more than one "discussion starter" in the code. I figured if nothing else that would have attracted the Flump.

-PatP

3. King of Understatement
Join Date
Feb 2004
Location
One Flump in One Place
Posts
14,912
To catch a fish such code is fitting. To catch a flump - why you only need call his name.

4. King of Understatement
Join Date
Feb 2004
Location
One Flump in One Place
Posts
14,912
Ok - the one thing that struck me when I first read it was why you insert 2 (a constant) many times in a loop. I don't understand why you insert a hard coded value, nor why in a loop instead of a set. Don't tell me know - I am indulging you by studying your code in more depth

5. World Class Flame Warrior
Join Date
Jun 2003
Location
Ohio
Posts
12,595
Sorry. I have no time for mssqlbation today....

6. Registered User
Join Date
Dec 2007
Location
Richmond, VA
Posts
1,328
Hey Pat,
I did some advertising for you on the DB2 side of the forum. As there is a guy over there who loves this kind of stuff. He has a sudoku solver over there that he posts about.
Dave

7. King of Understatement
Join Date
Feb 2004
Location
One Flump in One Place
Posts
14,912
Oh for Chrissake. You've included code just for the mischievousness of it.

Very unprofessional - I would never dream of such a thing.

Well, apart from yesterday in a QAD archiving script
Code:
`SELECT * INTO tabby FROM tabbyWabby WHERE 1^21=17`

8. Registered User
Join Date
Jul 2009
Location
NY
Posts
963

## How it's simple in DB2

Code:
```with number (number) as
(select int(2010) from sysibm.sysdummy1
)
,
factors(fact) as
(select 2 from sysibm.sysdummy1
union all
select fact + 1
from factors, number
where fact + 1 <= number
)
,
Prime_Factorization (in_number, remd, Prime_Factorization) as
(select number, number, varchar('1', 1000)
from number
union all
select in_number, int(remd / fact), Prime_Factorization || ' * ' || varchar(fact)
from Prime_Factorization, factors
where mod(remd, fact) = 0 and remd > 1
and fact = (select min(fact) from factors where mod(remd, fact) = 0 )
)
select in_number "Number", Prime_Factorization "Prime Factorization of number"
from Prime_Factorization
where remd = 1```
Result:

Number.... Prime Factorization of number
2010....... 1 * 2 * 3 * 5 * 67
Lenny

P.S. Thanks for dav1mo for his remembering

9. Resident Curmudgeon
Join Date
Feb 2004
Location
In front of the computer
Posts
15,579
I'm pretty sure that Lenny's DB2 solution will determine which prime numbers are factors of the argument, but not how many times they are factors of it. Consdier the following output as an example:
Code:
```-----------
0

(1 row(s) affected)

v
-------------------- -----------
2                    2
3                    3
5                    5
7                    7

(4 row(s) affected)

--------------------
277945762500

(1 row(s) affected)```
-PatP

10. Registered User
Join Date
Jul 2009
Location
NY
Posts
963

## DB2 made EASY

Originally Posted by Pat Phelan
I'm pretty sure that Lenny's DB2 solution will determine which prime numbers are factors of the argument, but not how many times they are factors of it. Consdier the following output as an example:
Code:
```-----------
0

(1 row(s) affected)

v
-------------------- -----------
2                    2
3                    3
5                    5
7                    7

(4 row(s) affected)

--------------------
277945762500

(1 row(s) affected)```
-PatP
This one is much easier than you are thinking about:

1. Original, which I changed from INTEGER to DECIMAL:

Code:
```with number (number) as
(select decimal(277945762500, 15, 0) from sysibm.sysdummy1
)
,
factors(fact) as
(select decimal(2, 15, 0)  from sysibm.sysdummy1
union all
select fact + 1
from factors, number
where fact + 1 <= sqrt(2 * number)
union all
select number
from number
)
,
Prime_Factorization (in_number, remd, Prime_Factorization) as
(select number, number, varchar('1', 1000)
from number
union all
select in_number, decimal(remd / fact, 15, 0),
Prime_Factorization || ' * ' || strip(varchar(fact), t, '.')
from Prime_Factorization, factors
where mod(remd, fact) = 0 and remd > 1
and fact = (select min(fact) from factors where mod(remd, fact) = 0 )
)
select in_number "Number", Prime_Factorization "Prime Factorization of number"
from Prime_Factorization
where remd = 1```
Result:

Number.............................. Prime Factorization of number
277945762500....... 1 * 2 * 2 * 3 * 3 * 3 * 5 * 5 * 5 * 5 * 5 * 7 * 7 * 7 * 7 * 7 * 7 * 7
The next query I changed in your way:

Code:
```with number (number) as
(select decimal(277945762500, 15, 0) from sysibm.sysdummy1
)
,
factors(fact) as
(select decimal(2, 15, 0)  from sysibm.sysdummy1
union all
select fact + 1
from factors, number
where fact + 1 <= sqrt(2 * number)
union all
select number
from number
)
,
Prime_Factorization (in_number, remd, fact) as
(select number, number, 1
from number
union all
select in_number, decimal(pf.remd / f1.fact, 15, 0), f1.fact
from Prime_Factorization pf, factors f1
where mod(pf.remd, f1.fact) = 0 and pf.remd > 1
and f1.fact = (select min(f2.fact) from factors f2
where mod(pf.remd, fact) = 0 )
)
select distinct in_number "Number",
nullif(0, 0) "Prime Factor", nullif(0, 0) "Factor Power"
from Prime_Factorization
union all
select nullif(0, 0) "Number", fact "Prime Factor", count(*) "Factor Power"
from Prime_Factorization
where fact > 1
group by fact```
And we got the result:

Number......... Prime Factor......... Factor Power
277945762500
.......................... 2........................... 2
.......................... 3........................... 3
.......................... 5........................... 5
.......................... 7........................... 7
With respect, Lenny
Last edited by Lenny77; 06-16-10 at 18:21.

11. Resident Curmudgeon
Join Date
Feb 2004
Location
In front of the computer
Posts
15,579
I was concerned the the original solution would simply determine that the argument was divisible by a prime (such as 2), but not the power of 2. I was mistaken.

Unfortunately I don't have a current version of DB2 to test code and concepts... I'm supporting zOS DB2 v7.1 and that is all that I've got access to at the moment. I'm accustomed to later versions of DB2, and the client now has an upgrade project in place so hopefully I'll be able to play with my old toys (DB2 8.x and possibly 9.x) again soon!

I'm just curious, but what kind of run times are you getting and what kind of hardware are you using to get those runtimes? I'm processing JOINS that rely on the results of a revised version of my code that are handling over 2500 rows per second with 10-17 digit numbers being factored on both tables using a 4 Gb laptop, and the performance shocked me.

-PatP

12. Registered User
Join Date
Jul 2009
Location
NY
Posts
963
Originally Posted by Pat Phelan
I was concerned the the original solution would simply determine that the argument was divisible by a prime (such as 2), but not the power of 2. I was mistaken.

Unfortunately I don't have a current version of DB2 to test code and concepts... I'm supporting zOS DB2 v7.1 and that is all that I've got access to at the moment. I'm accustomed to later versions of DB2, and the client now has an upgrade project in place so hopefully I'll be able to play with my old toys (DB2 8.x and possibly 9.x) again soon!

I'm just curious, but what kind of run times are you getting and what kind of hardware are you using to get those runtimes? I'm processing JOINS that rely on the results of a revised version of my code that are handling over 2500 rows per second with 10-17 digit numbers being factored on both tables using a 4 Gb laptop, and the performance shocked me.

-PatP
I'm agree with you:
"In theory, theory and practice are identical. In practice, theory and practice are unrelated"....

Lenny

13. Registered User
Join Date
Jul 2009
Location
NY
Posts
963

## From Theory to Practice

Yesterday my query worked for more than 45 second...
It was the theory of programming - Idea.
Today I modified the query to get result in 1 second.
This is a practice of programming - Optimization.

Optimized query:

Code:
```with number (number) as
(select decimal(277945762500, 15, 0) from sysibm.sysdummy1
)
,
fact1(fact) as
(
select decimal(3, 15, 0)   from sysibm.sysdummy1
union all
select fact + 2
from fact1, number
where fact + 2 <= sqrt(number) + 1
)
,
factors(fact) as
(
select 2 from sysibm.sysdummy1
union all
select * from fact1
)
,
Prime_Factorization (in_number, remd, fact) as
(select number, number, 1
from number
union all
select in_number, decimal(pf.remd / coalesce(f1.fact, pf.remd) , 15, 0),
coalesce(f1.fact, pf.remd)
from Prime_Factorization pf,
table (select min(f2.fact) fact
from factors f2
where mod(pf.remd, f2.fact) = 0
and f2.fact <= sqrt(pf.remd) + 1  ) f1
where pf.remd > 1
)
select distinct in_number "Number",
nullif(0, 0) "Prime Factor", nullif(0, 0) "Factor Power"
from Prime_Factorization
union all
select nullif(0, 0) "Number", fact "Prime Factor", count(*) "Factor Power"
from Prime_Factorization
where fact > 1
group by fact```
And we got the same result:

Number......... Prime Factor......... Factor Power
277945762500
.......................... 2........................... 2
.......................... 3........................... 3
.......................... 5........................... 5
.......................... 7........................... 7
With respect, Lenny
Last edited by Lenny77; 06-17-10 at 19:02.

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•