## 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.

### 14 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
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;

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

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