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;
answer INTEGER := 0;
    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
            answer := y;
            EXIT;
        END IF;
    END LOOP;
    
dbms_output.put_line(answer);

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
        answer := 2;
        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;
        answer := 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;
    
dbms_output.put_line(answer);

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

-- output: 6857

Questions or comments? Feel free to leave them below or reach out to me on Twitter!