# Thread: Prime Factors for Lenny77

1. Registered User
Join Date
Dec 2007
Location
Richmond, VA
Posts
1,328

## Unanswered: 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/microsoft-sq...ing-t-sql.html
Dave

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

## Thank You for your remembering

At least it works for any integer numbers.

Thanks, Lenny

3. Registered 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```
Result:

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

4. Registered 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```
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

5. Registered 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```
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 17:59.

#### Posting Permissions

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