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

## Solutions

### #1: Using CTE (recursive WITH)

WITH input AS ( SELECT &N n FROM dual ), x(num, flag) AS ( SELECT 2, CASE WHEN MOD(n, 2)=0 THEN 1 ELSE 0 END AS flag FROM input UNION ALL SELECT x.num+1, CASE WHEN MOD(i.n, x.num+1)=0 THEN 1 ELSE 0 END FROM input i, x WHERE x.num+1<=i.n ), y AS ( SELECT num, (SELECT CASE WHEN COUNT(*)=2 THEN 1 ELSE 0 END FROM dual WHERE MOD(x.num,LEVEL)=0 CONNECT BY LEVEL<=x.num) is_prime FROM x WHERE flag=1 ) SELECT MAX(num) "Biggest Prime Factor" FROM y WHERE is_prime=1; Enter value for n: 100 old 2: SELECT &N n new 2: SELECT 100 n Biggest Prime Factor -------------------- 5 SQL> / Enter value for n: 52 old 2: SELECT &N n new 2: SELECT 52 n Biggest Prime Factor -------------------- 13 SQL> / Enter value for n: 21 old 2: SELECT &N n new 2: SELECT 21 n Biggest Prime Factor -------------------- 7

### #2: Using CONNECT BY clause , version 1

WITH input AS ( SELECT &N n FROM dual ), x AS ( SELECT LEVEL num FROM input i WHERE MOD(i.N, LEVEL)=0 CONNECT BY LEVEL<=i.N ), y AS ( SELECT num, (SELECT CASE WHEN COUNT(*)=2 THEN 1 ELSE 0 END FROM dual WHERE MOD(x.num,LEVEL)=0 CONNECT BY LEVEL<=x.num) is_prime FROM x WHERE flag=1 ) SELECT MAX(num) "Biggest Prime Factor" FROM y WHERE is_prime=1;

### #3: Using CONNECT BY clause, version 2

WITH input AS ( SELECT &N n FROM dual ), range AS ( SELECT LEVEL num FROM input i CONNECT BY LEVEL <= i.N ), x AS( SELECT r1.num FROM range r1, range r2, input i WHERE MOD(i.N, r1.num)=0 GROUP BY r1.num HAVING COUNT(CASE WHEN MOD(r1.num, r2.num)=0 THEN 1 END)=2 ) SELECT MAX(num) "Biggest Prime Factor" FROM x;

**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