Page 1 of 2 12 LastLast
Results 1 to 15 of 25
  1. #1
    Join Date
    Jul 2009
    Location
    NY
    Posts
    963

    Lightbulb Unanswered: Prime numbers (plain DB2)

    In mathematics, a prime number (or a prime) is a natural number which has exactly two distinct natural number divisors: 1 and itself. The first twenty-five prime numbers are:

    2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97....

    To find prime numbers we'll use the theorem:
    If for number N not exists divisor 1 < k <= Sqrt(N) then N is the prime.

    Base on this theorem we'll create the DB2 query:


    Code:
    with 
    limit (lim) as 
    (select int(10000) from sysibm.sysdummy1
    )
    ,
    numbers (num) as 
    (select 2 from sysibm.sysdummy1
    union all 
    select num + 1 from numbers, limit
    where num + 1 <= int(sqrt(lim)) + 1
    ) 
    ,
    prime_nbr(prime_num, prime_ind) as
    (select int(2), varchar('P', 1) from sysibm.sysdummy1
    union all 
    select 3, 'P' from sysibm.sysdummy1
    union all 
    select prime_num + 2, 'P' 
    from prime_nbr, limit
    where 
    prime_num + 2 <= lim
    and
    not exists 
    (select 1 from numbers
    where num <= int(sqrt(prime_num )) + 1
    and
    prime_num + 2 = int((prime_num + 2) / num) * num ) 
    union all 
    select prime_num + 2, 'R' 
    from prime_nbr, limit
    where 
    prime_num + 2 <= lim
    and
    exists 
    (select 1 from numbers
    where num <= int(sqrt(prime_num )) + 1
    and
    prime_num + 2 = int((prime_num + 2) / num) * num ) 
    ) 
    select prime_num "prime number" from prime_nbr
    where prime_ind = 'P'
    You will spend just 2 seconds to get all primes from 2 to 10000.

    You will get 1229 primes in RS. No formula exists for prime number, but computerization can help us in many problems.


    Lenny K.
    Last edited by sathyaram_s; 07-23-09 at 11:53. Reason: changed quote tag to code tag

  2. #2
    Join Date
    Jul 2009
    Location
    NY
    Posts
    963
    Changing lim in the limit table you can get the different sets of prime numbers.

    Lenny K.

  3. #3
    Join Date
    Jul 2006
    Location
    Pune , India
    Posts
    433
    my try... not able to pick 2,3 though

    with temp(no) as (select row_number() over() from syscat.columns fetch first 100 rows only ),
    temp2(no ,remainder) as (select t1.no , mod(t1.no , t2.no) from temp t1 , temp t2
    where t2.no <= sqrt (t1.no) and t2.no <> 1
    )
    select no from temp2 group by no having no* min(remainder) <> 0
    Rahul Singh
    Certified DB2 9 DBA / Application Developer

  4. #4
    Join Date
    Jul 2006
    Location
    Pune , India
    Posts
    433
    this will complete:

    select no from (values (2),(3) ) as t(no) where no in (select no from temp)
    union
    select no from temp2 group by no having no* min(remainder) <> 0
    Rahul Singh
    Certified DB2 9 DBA / Application Developer

  5. #5
    Join Date
    Jul 2009
    Location
    NY
    Posts
    963
    Thanks for reply. I don't have v9, yet.

    Lenny

  6. #6
    Join Date
    Jul 2009
    Location
    NY
    Posts
    963
    The next step, as usual is simplification and optimization of the basic query:

    with
    limit (lim) as
    (select int(10000) from sysibm.sysdummy1
    )
    ,
    numbers (num) as
    (select 2 from sysibm.sysdummy1
    union all
    select num + 1 from numbers, limit
    where num + 1 <= int(sqrt(lim)) + 1
    )
    ,
    prime_check (prime_num, prime_ind) as
    (select int(2), varchar('P', 1) from sysibm.sysdummy1
    union all
    select 3, 'P' from sysibm.sysdummy1
    union all
    select prime_num + 2,
    case
    when
    1 = (select 1 from sysibm.sysdummy1
    where
    exists
    (select 1 from numbers
    where num <= int(sqrt(prime_num )) + 1
    and
    prime_num + 2 = int((prime_num + 2) / num) * num ) )
    then 'R'
    else 'P'
    end
    from prime_check, limit
    where
    prime_num + 2 <= lim
    )
    ,
    prime_num_1 (prime_num) as
    (select prime_num from prime_check
    where prime_ind = 'P'
    )
    select prime_num "prime number" from prime_num_1

    Lenny K.

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

    Thumbs up

    The complete query which is optimized (basic query get first 1,000,000
    primary numbers in more then 1 hours. The last one in 5 minutes):


    with
    limit (lim) as
    (select int(100000) from sysibm.sysdummy1
    )
    ,
    numbers (num) as
    (select 2 from sysibm.sysdummy1
    union all
    select num + 1 from numbers, limit
    where num + 1 <= int(sqrt(lim)) + 1
    )
    ,
    prime_check (prime_num, prime_ind) as
    (select int(2), varchar('P', 1) from sysibm.sysdummy1
    union all
    select 3, 'P' from sysibm.sysdummy1
    union all
    select prime_num + 2,
    case
    when
    1 = (select 1 from sysibm.sysdummy1
    where
    exists
    (select 1 from numbers
    where num <= int(sqrt(prime_num)) + 1
    and
    prime_num + 2 = int((prime_num + 2) / num) * num ) )
    then 'R'
    else 'P'
    end
    from prime_check, limit
    where
    prime_num + 2 <= int(sqrt(lim)) + 1
    )
    ,
    prime_num_1 (prime_num) as
    (select prime_num from prime_check
    where prime_ind = 'P'
    )
    ,
    prime_check_2 (prime_num, prime_ind) as
    (select max(prime_num), varchar('X', 1)
    from prime_num_1
    union all
    select p2.prime_num + 2,
    case
    when
    1 = (select 1 from sysibm.sysdummy1
    where exists
    (select 1 from prime_num_1 p1
    where p1.prime_num <= int(sqrt(p2.prime_num)) + 1
    and
    p2.prime_num + 2= int((p2.prime_num + 2) / p1.prime_num ) * p1.prime_num ) )
    then 'R'
    else 'P'
    end
    from prime_check_2 p2, limit lm
    where
    p2.prime_num + 2 <= lim
    )
    ,
    prime_number (prime_num) as
    (select * from prime_num_1
    union All
    select prime_num from prime_check_2
    where prime_ind = 'P'
    )
    select prime_num "Prime Number"
    from prime_number
    Lenny K.
    Last edited by Lenny77; 07-24-09 at 15:45.

  8. #8
    Join Date
    Jul 2009
    Posts
    150

    Question

    Maybe is good idea to replace:
    prime_num + 2 = int((prime_num + 2) / num) * num ) )
    with
    0 = mode(prime_num + 2, num) ?
    Last edited by DB2Plus; 07-25-09 at 14:32.

  9. #9
    Join Date
    Apr 2002
    Location
    Toronto, Canada
    Posts
    20,002
    hey lenny check this out -- Celko's Summer SQL Stumpers: Prime Numbers

    you should enter the contest

    don't forget the last point: 5) Explain how you got your answer.

    rudy.ca | @rudydotca
    Buy my SitePoint book: Simply SQL

  10. #10
    Join Date
    Jul 2009
    Location
    NY
    Posts
    963
    Quote Originally Posted by r937
    hey lenny check this out -- Celko's Summer SQL Stumpers: Prime Numbers

    you should enter the contest

    don't forget the last point: 5) Explain how you got your answer.

    Thank you for link. I did it.

    Lenny.

  11. #11
    Join Date
    Jul 2009
    Location
    NY
    Posts
    963
    Thank you, DB2Plus.

    I replaced the equaty num = p * (num / p) by mod(num, p) = 0.

    It's not improve the performance, but looks more compact:

    with
    limit (lim) as
    (select int(100000) from sysibm.sysdummy1
    )
    ,
    numbers (num) as
    (select 2 from sysibm.sysdummy1
    union all
    select num + 1 from numbers, limit
    where num + 1 <= int(sqrt(lim)) + 1
    )
    ,
    prime_check (prime_num, prime_ind) as
    (select int(2), varchar('P', 1) from sysibm.sysdummy1
    union all
    select 3, 'P' from sysibm.sysdummy1
    union all
    select prime_num + 2,
    case
    when
    1 = (select 1 from sysibm.sysdummy1
    where exists
    (select 1 from numbers
    where
    num <= int(sqrt(prime_num)) + 1
    and mod(prime_num + 2, num) = 0 ) )
    then 'R' else 'P'
    end
    from prime_check, limit
    where
    prime_num + 2 <= int(sqrt(lim)) + 1
    )
    ,
    prime_num_1 (prime_num) as
    (select prime_num from prime_check
    where prime_ind = 'P'
    )
    ,
    prime_check_2 (prime_num, prime_ind) as
    (select max(prime_num), varchar('X', 1)
    from prime_num_1
    union all
    select p2.prime_num + 2,
    case
    when
    1 = (select 1 from sysibm.sysdummy1
    where exists
    (select 1 from prime_num_1 p1
    where
    p1.prime_num <= int(sqrt(p2.prime_num)) + 1
    and mod(p2.prime_num + 2, p1.prime_num) = 0 ) )
    then 'R' else 'P'
    end
    from prime_check_2 p2, limit lm
    where
    p2.prime_num + 2 <= lim
    )
    ,
    prime_number (prime_num) as
    (select * from prime_num_1
    union all
    select prime_num from prime_check_2
    where prime_ind = 'P'
    )
    select prime_num "Prime Number"
    from prime_number
    Lenny K.

  12. #12
    Join Date
    Jul 2006
    Location
    Pune , India
    Posts
    433
    Quote Originally Posted by Lenny77
    Thanks for reply. I don't have v9, yet.

    Lenny
    ?? which function is not compatible with v8 luw (i can see article from 2004 describing row_number() over() :
    Using DB2 UDB OLAP functions
    )
    are you on z-os ?
    Rahul Singh
    Certified DB2 9 DBA / Application Developer

  13. #13
    Join Date
    Jul 2009
    Location
    NY
    Posts
    963
    Quote Originally Posted by rahul_s80
    ?? which function is not compatible with v8 luw (i can see article from 2004 describing row_number() over() :
    Using DB2 UDB OLAP functions
    )
    are you on z-os ?
    I am working on OS390.

    Anyway, thanks. I understood what you mean.

  14. #14
    Join Date
    Jul 2009
    Location
    NY
    Posts
    963
    Using some simple divisibility rules we can improve performance of the query in times !

    with
    limit (lim) as
    (select int(100000) from sysibm.sysdummy1
    )
    ,
    numbers (num) as
    (select 2 from sysibm.sysdummy1
    union all
    select num + 1 from numbers, limit
    where num + 1 <= int(sqrt(lim)) + 1
    )
    ,
    prime_check (prime_num, prime_ind) as
    (select int(2), varchar('P', 1) from sysibm.sysdummy1
    union all
    select 3, 'P' from sysibm.sysdummy1
    union all
    select prime_num + 2,
    case
    when
    1 = (select 1 from sysibm.sysdummy1
    where exists
    (select 1 from numbers
    where
    num <= int(sqrt(prime_num)) + 1
    and mod(prime_num + 2, num) = 0 ) )
    then 'R' else 'P'
    end
    from prime_check, limit
    where
    prime_num + 2 <= int(sqrt(lim)) + 1
    )
    ,
    prime_num_1 (prime_num) as
    (select prime_num from prime_check
    where prime_ind = 'P'
    )
    ,
    prime_check_2 (prime_num, prime_ind) as
    (select max(prime_num), varchar('X', 1)
    from prime_num_1
    union all
    select p2.prime_num + 2,
    case
    when int(substr(digits(p2.prime_num + 2), 10, 1)) = 5 then 'R'
    when
    mod(
    int(substr(digits(p2.prime_num + 2 ), 1, 1)) + int(substr(digits(p2.prime_num + 2 ), 2, 1)) +
    int(substr(digits(p2.prime_num + 2 ), 3, 1)) + int(substr(digits(p2.prime_num + 2 ), 4, 1)) +
    int(substr(digits(p2.prime_num + 2 ), 5, 1)) + int(substr(digits(p2.prime_num + 2 ), 6, 1)) +
    int(substr(digits(p2.prime_num + 2 ), 7, 1)) + int(substr(digits(p2.prime_num + 2 ), 8, 1)) +
    int(substr(digits(p2.prime_num + 2 ), 9, 1)) + int(substr(digits(p2.prime_num + 2 ), 10, 1)), 3) = 0
    then 'R'
    when
    mod(
    int(substr(digits(p2.prime_num + 2 ), 1, 1)) - int(substr(digits(p2.prime_num + 2 ), 2, 1)) +
    int(substr(digits(p2.prime_num + 2 ), 3, 1)) - int(substr(digits(p2.prime_num + 2 ), 4, 1)) +
    int(substr(digits(p2.prime_num + 2 ), 5, 1)) - int(substr(digits(p2.prime_num + 2 ), 6, 1)) +
    int(substr(digits(p2.prime_num + 2 ), 7, 1)) - int(substr(digits(p2.prime_num + 2 ), 8, 1)) +
    int(substr(digits(p2.prime_num + 2 ), 9, 1)) - int(substr(digits(p2.prime_num + 2 ), 10, 1)), 11) = 0
    then 'R'
    when
    1 = (select 1 from sysibm.sysdummy1
    where exists
    (select 1 from prime_num_1 p1
    where
    p1.prime_num <= int(sqrt(p2.prime_num)) + 1
    and mod(p2.prime_num + 2, p1.prime_num) = 0 ) )
    then 'R' else 'P'
    end
    from prime_check_2 p2, limit lm
    where
    p2.prime_num + 2 <= lim
    )
    ,
    prime_number (prime_num) as
    (select * from prime_num_1
    union all
    select prime_num from prime_check_2
    where prime_ind = 'P'
    )
    select prime_num "Prime Number"
    from prime_number
    Lenny
    Last edited by Lenny77; 08-28-09 at 16:19.

  15. #15
    Join Date
    Jul 2009
    Location
    NY
    Posts
    963
    Finally, we can add some divisibility rules by 7. It will optimize our query, too.

    with
    limit (lim) as
    (select int(1000000) from sysibm.sysdummy1
    )
    ,
    numbers (num) as
    (select 2 from sysibm.sysdummy1
    union all
    select num + 1 from numbers, limit
    where num + 1 <= int(sqrt(lim)) + 1
    )
    ,
    prime_check (prime_num, prime_ind) as
    (select int(2), varchar('P', 1) from sysibm.sysdummy1
    union all
    select 3, 'P' from sysibm.sysdummy1
    union all
    select prime_num + 2,
    case
    when int(substr(digits(prime_num + 2), 10, 1)) = 5 and prime_num + 2 > 5 then 'R'
    when
    mod(
    int(substr(digits(prime_num + 2 ), 1, 1)) + int(substr(digits(prime_num + 2 ), 2, 1)) +
    int(substr(digits(prime_num + 2 ), 3, 1)) + int(substr(digits(prime_num + 2 ), 4, 1)) +
    int(substr(digits(prime_num + 2 ), 5, 1)) + int(substr(digits(prime_num + 2 ), 6, 1)) +
    int(substr(digits(prime_num + 2 ), 7, 1)) + int(substr(digits(prime_num + 2 ), 8, 1)) +
    int(substr(digits(prime_num + 2 ), 9, 1)) + int(substr(digits(prime_num + 2 ), 10, 1)), 3) = 0
    and prime_num + 2 > 3
    then 'R'
    when
    mod(
    int(substr(digits(prime_num + 2 ), 1, 1)) - int(substr(digits(prime_num + 2 ), 2, 1)) +
    int(substr(digits(prime_num + 2 ), 3, 1)) - int(substr(digits(prime_num + 2 ), 4, 1)) +
    int(substr(digits(prime_num + 2 ), 5, 1)) - int(substr(digits(prime_num + 2 ), 6, 1)) +
    int(substr(digits(prime_num + 2 ), 7, 1)) - int(substr(digits(prime_num + 2 ), 8, 1)) +
    int(substr(digits(prime_num + 2 ), 9, 1)) - int(substr(digits(prime_num + 2 ), 10, 1)), 11) = 0
    and prime_num + 2 > 11
    then 'R'

    when
    1 = (select 1 from sysibm.sysdummy1
    where exists
    (select 1 from numbers
    where
    num <= int(sqrt(prime_num)) + 1
    and mod(prime_num + 2, num) = 0 ) )
    then 'R' else 'P'
    end
    from prime_check, limit
    where
    prime_num + 2 <= int(sqrt(lim)) + 1
    )
    ,
    prime_num_1 (prime_num) as
    (select prime_num from prime_check
    where prime_ind = 'P'
    )
    ,
    prime_check_2 (prime_num, prime_ind) as
    (select max(prime_num), varchar('X', 1)
    from prime_num_1
    union all
    select p2.prime_num + 2,
    case
    when int(substr(digits(p2.prime_num + 2), 10, 1)) = 5 then 'R'
    when
    mod(
    int(substr(digits(p2.prime_num + 2 ), 1, 1)) + int(substr(digits(p2.prime_num + 2 ), 2, 1)) +
    int(substr(digits(p2.prime_num + 2 ), 3, 1)) + int(substr(digits(p2.prime_num + 2 ), 4, 1)) +
    int(substr(digits(p2.prime_num + 2 ), 5, 1)) + int(substr(digits(p2.prime_num + 2 ), 6, 1)) +
    int(substr(digits(p2.prime_num + 2 ), 7, 1)) + int(substr(digits(p2.prime_num + 2 ), 8, 1)) +
    int(substr(digits(p2.prime_num + 2 ), 9, 1)) + int(substr(digits(p2.prime_num + 2 ), 10, 1)), 3) = 0
    then 'R'
    when
    mod(
    6 * int(substr(digits(p2.prime_num + 2 ), 1, 1)) + 2 * int(substr(digits(p2.prime_num + 2 ), 2, 1)) +
    3 * int(substr(digits(p2.prime_num + 2 ), 3, 1)) + 1 * int(substr(digits(p2.prime_num + 2 ), 4, 1)) +
    5 * int(substr(digits(p2.prime_num + 2 ), 5, 1)) + 4 * int(substr(digits(p2.prime_num + 2 ), 6, 1)) +
    6 * int(substr(digits(p2.prime_num + 2 ), 7, 1)) + 2 * int(substr(digits(p2.prime_num + 2 ), 8, 1)) +
    3 * int(substr(digits(p2.prime_num + 2 ), 9, 1)) + 1 * int(substr(digits(p2.prime_num + 2 ), 10, 1)), 7) = 0
    then 'R'
    when
    mod(
    int(substr(digits(p2.prime_num + 2 ), 1, 1)) - int(substr(digits(p2.prime_num + 2 ), 2, 1)) +
    int(substr(digits(p2.prime_num + 2 ), 3, 1)) - int(substr(digits(p2.prime_num + 2 ), 4, 1)) +
    int(substr(digits(p2.prime_num + 2 ), 5, 1)) - int(substr(digits(p2.prime_num + 2 ), 6, 1)) +
    int(substr(digits(p2.prime_num + 2 ), 7, 1)) - int(substr(digits(p2.prime_num + 2 ), 8, 1)) +
    int(substr(digits(p2.prime_num + 2 ), 9, 1)) - int(substr(digits(p2.prime_num + 2 ), 10, 1)), 11) = 0
    then 'R'
    when
    1 = (select 1 from sysibm.sysdummy1
    where exists
    (select 1 from prime_num_1 p1
    where
    p1.prime_num <= int(sqrt(p2.prime_num)) + 1
    and mod(p2.prime_num + 2, p1.prime_num) = 0 ) )
    then 'R' else 'P'
    end
    from prime_check_2 p2, limit lm
    where
    p2.prime_num + 2 <= lim
    )
    ,
    prime_number (prime_num) as
    (select * from prime_num_1
    union all
    select prime_num from prime_check_2
    where prime_ind = 'P'
    )
    select prime_num "Prime Number"
    from prime_number
    Lenny

Posting Permissions

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