Results 1 to 5 of 5
Thread: Prime Factors for Lenny77

061610, 10:52 #1Registered User
 Join Date
 Dec 2007
 Location
 Richmond, VA
 Posts
 1,328
Provided Answers: 5Unanswered: 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.
http://www.dbforums.com/microsoftsq...ingtsql.html
Dave

061610, 12:48 #2Registered User
 Join Date
 Jul 2009
 Location
 NY
 Posts
 963
Thank You for your remembering
At least it works for any integer numbers.
Thanks, Lenny

061610, 13:00 #3Registered User
 Join Date
 Jul 2009
 Location
 NY
 Posts
 963
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
Number.... Prime Factorization of number
2010....... 1 * 2 * 3 * 5 * 67

061610, 17:23 #4Registered User
 Join Date
 Jul 2009
 Location
 NY
 Posts
 963
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
Number.............................. Prime Factorization of number
277945762500....... 1 * 2 * 2 * 3 * 3 * 3 * 5 * 5 * 5 * 5 * 5 * 7 * 7 * 7 * 7 * 7 * 7 * 7
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
Number......... Prime Factor......... Factor Power
277945762500
.......................... 2........................... 2
.......................... 3........................... 3
.......................... 5........................... 5
.......................... 7........................... 7
Link: http://www.dbforums.com/microsoftsq...ingtsql.html

061710, 16:19 #5Registered User
 Join Date
 Jul 2009
 Location
 NY
 Posts
 963
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
Number......... Prime Factor......... Factor Power
277945762500
.......................... 2........................... 2
.......................... 3........................... 3
.......................... 5........................... 5
.......................... 7........................... 7Last edited by Lenny77; 061710 at 17:59.