| |
|
If this is your first visit, be sure to check out the FAQ by clicking the link above.
You may have to register before you can post: click the register link above to proceed.
To start viewing messages, select the forum that you want to visit from the selection below.
|
 |
06-16-10, 10:52
|
|
Registered User
|
|
Join Date: Dec 2007
Location: Richmond, VA
Posts: 782
|
|
|
Prime Factors for Lenny77
|
|
One of the guys on the SQL Server forum on here posted SQL for prime factors that I thought was right up your alley Lenny.
Prime factors using T-SQL
Dave
|
|
06-16-10, 12:48
|
|
Registered User
|
|
Join Date: Jul 2009
Location: NY
Posts: 886
|
|
Thank You for your remembering
At least it works for any integer numbers.
Thanks, Lenny
|
|
06-16-10, 13:00
|
|
Registered User
|
|
Join Date: Jul 2009
Location: NY
Posts: 886
|
|
|
How it works
|
|
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:
Quote:
Number.... Prime Factorization of number
2010....... 1 * 2 * 3 * 5 * 67
|
Lenny
|
|
06-16-10, 17:23
|
|
Registered User
|
|
Join Date: Jul 2009
Location: NY
Posts: 886
|
|
My answer to Pat Phelan
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:
Quote:
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:
Quote:
Number......... Prime Factor......... Factor Power
277945762500
.......................... 2........................... 2
.......................... 3........................... 3
.......................... 5........................... 5
.......................... 7........................... 7
|
With respect, Lenny
Link: Prime factors using T-SQL
|
|
06-17-10, 16:19
|
|
Registered User
|
|
Join Date: Jul 2009
Location: NY
Posts: 886
|
|
From Idea to Optimized Query
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 seconds.
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:
Quote:
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 17:59.
|
| Thread Tools |
Search this Thread |
|
|
|
| Display Modes |
 Linear Mode
|
Posting Rules
|
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts
HTML code is Off
|
|
|
|
|
dBforums
>
Prime Factors for Lenny77
