Puzzle of the Week #16: Find the Biggest Prime Factor

Puzzle of the Week #16:

With a single SELECT statement find the biggest prime factor of a given integer value (N).

Expected Result:

--For N=100:

Biggest Prime Factor
--------------------
                  5

--For N=52:

Biggest Prime Factor
--------------------
                 13

--For N=21:

Biggest Prime Factor
--------------------
                   7

To submit your answer (one or more!) please start following this blog and add a comment to this post.

A correct answer (and workarounds!) will be published here in a week.

My Oracle Group on Facebook:

If you like this post, you may want to join my new Oracle group on Facebook: https://www.facebook.com/groups/sqlpatterns/

Would you like to read about many more tricks and puzzles?

For more tricks and cool techniques check my book “Oracle SQL Tricks and Workarounds” for instructions.

Advertisements

13 thoughts on “Puzzle of the Week #16: Find the Biggest Prime Factor

  1. sajith June 21, 2016 / 11:01 am

    with a as (
    select num1 prime_number
    from (select level num1 from dual connect by level <= :n)
    , (select level num2 from dual connect by level <= :n)
    where num2<=num1
    group by num1
    having count(case num1/num2 when trunc(num1/num2) then '0' end) = 2
    )
    select max(prime_number) from a

    • Zahar Hilkevich June 27, 2016 / 2:39 pm

      This query returns biggest PRIME number that is not bigger than the input parameter (:n), but we need the biggest prime FACTOR.

  2. Ashwin Kumar Padhy June 22, 2016 / 11:03 am

    DECLARE
    target INTEGER := 100;
    current_factor INTEGER := 2;
    answer INTEGER := 1;
    PROCEDURE remove_factors(int_in INTEGER)
    IS
    BEGIN
    IF REMAINDER(target, int_in) = 0
    THEN
    answer := int_in;
    target := target/int_in;
    WHILE REMAINDER(target, int_in) = 0
    LOOP
    target := target/int_in;
    END LOOP;
    END IF;
    END;
    BEGIN
    WHILE target > 1
    LOOP
    IF current_factor = 2
    THEN
    remove_factors(current_factor);
    current_factor := 3;
    ELSE
    remove_factors(current_factor);
    current_factor := current_factor + 2;
    END IF;
    END LOOP;

    dbms_output.put_line(answer);

    END;

  3. Krishna Jamal June 22, 2016 / 12:44 pm

    WITH a AS (SELECT &num p FROM Dual),
    b AS (SELECT l FROM
    (SELECT LEVEL l FROM a CONNECT BY LEVEL <= p),
    (SELECT LEVEL m FROM a CONNECT BY LEVEL <= p)
    GROUP BY l
    HAVING COUNT(DECODE(MOD(l,m), 0, 'P'))=1 OR
    COUNT(DECODE(MOD(l,m), 0, 'P'))=2)
    SELECT MAX(l) Biggest_Prime_Factor
    FROM a, b WHERE MOD(p, l) = 0;

    • Zahar Hilkevich June 27, 2016 / 2:20 pm

      The solution is OK, except 1 is not a prime number; so it should be excluded

  4. Pawan Kumar Khowal June 22, 2016 / 9:09 pm

    Solution 1

    DECLARE @ INT = 100

    ;WITH CTE AS
    (
    SELECT DISTINCT Number FROM Master..Spt_Values WHERE Number > 1 AND Number <= 1000
    )
    SELECT MAX(Number) Number FROM (
    SELECT Number FROM CTE
    EXCEPT
    (
    SELECT ( F1.number * F2.number ) a
    FROM CTE AS F1, CTE AS F2
    WHERE
    F1.Number BETWEEN 2 AND CEILING (SQRT (1000))
    AND F1.Number <= F2.Number
    AND (F1.Number * F2.Number) 1 AND Number = 2 AND Number 1
    AND num1.Number < num.Number
    AND num.Number % num1.Number = 0
    )

    )r
    WHERE @ % Number = 0

    GO

    Pawan Kumar Khowal

  5. Pawan Kumar Khowal June 22, 2016 / 9:10 pm

    Solution 2

    DECLARE @ INT = 21

    ;WITH CTE AS
    (
    SELECT DISTINCT Number FROM Master..Spt_Values WHERE Number > 1 AND Number = 2 AND Number 1
    AND num1.Number < num.Number
    AND num.Number % num1.Number = 0
    )

    )r
    WHERE @ % Number = 0

    GO

    Pawan Kumar Khowal

  6. Pawan Kumar Khowal June 22, 2016 / 9:11 pm

    DECLARE @ INT = 21

    ;WITH CTE AS
    (
    SELECT DISTINCT Number FROM Master..Spt_Values WHERE Number > 1 AND Number = 2 AND Number 1
    AND num1.Number < num.Number
    AND num.Number % num1.Number = 0
    )

    )r
    WHERE @ % Number = 0

  7. Ashwin Kumar Padhy June 23, 2016 / 1:02 am

    WITH s1 AS (SELECT LEVEL lv FROM dual CONNECT BY ROWNUM s3.ID) idd FROM s3)
    SELECT MAX(idd/ID) as “Biggest Prime Factor” FROM s4
    CONNECT BY ID=PRIOR IDd
    START WITH ID=1;

  8. Ashwin Kumar Padhy June 23, 2016 / 1:09 am

    WITH t AS
    (SELECT level l FROM dual CONNECT BY level :n) (l[DIM>TEMP[1]]=DECODE(mod(l[CV()],temp[1]),0,NULL,l[CV()]), temp[1]=MIN(l)[dim>temp[1]])
    )
    WHERE l IS NOT NULL
    )
    SELECT MAX(prim_num) AS “Biggest Prime Factor”
    FROM
    (SELECT *
    FROM t1 model dimension BY (rownum rn) measures(prim_num, :n val, 0 pow) rules iterate(1000) until (val[1]=1) (pow[ANY]
    ORDER BY rn = DECODE(mod(val[1],prim_num[CV()]),0,pow[CV()]+1,pow[CV()]), val[rn>1]
    ORDER BY rn = DECODE(mod(val[CV() -1],prim_num[CV()]),0,val[CV()-1]/prim_num[CV()],val[CV()-1]), val[1]=MIN(val)[ANY])
    )
    WHERE rn>1
    AND pow >0;

    • Zahar Hilkevich June 27, 2016 / 2:37 pm

      this query does not seem to be tested well – it gives error

  9. Ashwin Kumar Padhy June 23, 2016 / 1:10 am

    WITH s1 AS
    (SELECT LEVEL lv FROM dual CONNECT BY ROWNUM s3.ID
    ) idd
    FROM s3
    )
    SELECT MAX(idd/ID) AS “Biggest Prime Factor”
    FROM s4
    CONNECT BY ID=PRIOR IDd
    START WITH ID=1;

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s