# Project Euler in PL/SQL: Problem 3

Onward to the next problem from Project Euler. We’re getting more complex now, and I’ll need to introduce a subfunction for best results.

## Problem 3:

### Largest Prime Factor

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143?

```DECLARE
target INTEGER := 600851475143;
FUNCTION Is_Prime(num INTEGER)
RETURN BOOLEAN
IS
BEGIN
--we don't need to go beyond the square root, as any factors beyond will have a LCM below
FOR x IN 2..SQRT(num)
LOOP
IF REMAINDER(num, x) = 0
THEN
RETURN FALSE;
END IF;
END LOOP;

RETURN TRUE;
END;
BEGIN
--REVERSE since we're looking for the max value and we can stop once we find it
FOR y IN REVERSE 1..SQRT(target)
LOOP
--value must be a factor of target AND prime
IF REMAINDER(target,y) = 0 AND Is_Prime(y)
THEN
EXIT;
END IF;
END LOOP;

END;

-- output: 6857
```

This code get’s the the correct answer, but I made a mathematical assumption that could yield incorrect results in other cases. The range

`1..SQRT(target)`

does not cover all cases (such as 14, which has a GPF of 7). Utilizing some guidance from Project Euler, I was able to refactor (mostly just re-write…) the code into something that will work in all cases, but adds a layer of complexity and more loops.

```DECLARE
target INTEGER := 14;
current_factor INTEGER := 3;
answer INTEGER := 1; --tracks the GPF along the way
BEGIN
/*first check to see if we can reduce our possible range by dividing by 2
and we don't need to check any other even numbers*/
IF REMAINDER(target, 2) = 0
THEN
target := target/2;
WHILE REMAINDER(target, 2) = 0
LOOP
target := target/2;
END LOOP;
END IF;

WHILE target > 1
LOOP
/*same type of logic as above, this time starting with 3 and incrementing
to each odd number.*/
IF REMAINDER(target,current_factor) = 0
THEN
target := target/current_factor;
WHILE REMAINDER(target, current_factor) = 0
LOOP
target := target/current_factor;
END LOOP;
ELSE
current_factor := current_factor + 2;
END IF;
END LOOP;

END;

--output: 7
```

Now we have a perfectly working procedure! However, when I see code that repeats itself I have a strong urge to DRY it up. I refactored the code one final time to the below solution which utilizes a subprocedure to avoid repetition. I opted to leave our “target” number as a global level variable, but that could easily be refactored into the subprocedure as a parameter should we need to put it into a package or use it outside of Project Euler.

```DECLARE
target INTEGER := 600851475143;
current_factor INTEGER := 2;
answer INTEGER := 1; --tracks the GPF along the way
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;