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