Results 1 to 5 of 5
  1. #1
    Join Date
    Dec 2007
    Location
    Richmond, VA
    Posts
    1,328
    Provided Answers: 5

    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. #2
    Join Date
    Jul 2009
    Location
    NY
    Posts
    963

    Exclamation Thank You for your remembering

    At least it works for any integer numbers.

    Thanks, Lenny

  3. #3
    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. #4
    Join Date
    Jul 2009
    Location
    NY
    Posts
    963

    Thumbs up 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

    Link: http://www.dbforums.com/microsoft-sq...ing-t-sql.html

  5. #5
    Join Date
    Jul 2009
    Location
    NY
    Posts
    963

    Thumbs up 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 18: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
  •