Project Euler in PL/SQL: Problem 7

This Project Euler problem gave me some serious optimization issues as we deal with checking a wide range of numbers to see if they’re prime.

Problem 7:

10,001st Prime

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10 001st prime number?

This problem isn’t all that difficult to write a working procedure for; I’ve seen many of these same concepts from earlier Euler problems. I was able to put together the below code fairly quickly, but what wasn’t quick was the procedure itself. This brute-force approach did eventually reach the correct answer in ~4 minutes, but that’s much too slow. The process of checking every number between 2 and i-1 isn’t an optimized solution, though effective.

DECLARE
i PLS_INTEGER := 1; --current number being checked for prime-ness
prime_counter PLS_INTEGER := 0; --keeps track of how many primes we have found
prime BOOLEAN;
BEGIN
    WHILE prime_counter < 10001
    LOOP
    i:=i+1;
    prime := true;
        FOR x IN 2..i-1
        LOOP
            IF REMAINDER(i,x) = 0
            THEN
                --number isn't prime
                prime := false;
                exit;
            END IF;
        END LOOP;
        
        IF prime
        THEN
            prime_counter := prime_counter + 1;
        END IF;
    END LOOP;

    dbms_output.put_line(i);
END;

--output: 104743

I knew there had to be a better way to check if a number is prime, so I hit Google and found this Wikipedia article which gave me an algorithm I was able to convert to PL/SQL code, and I stored it in my new EULER_PKG for future use. Check out that link to see what’s going on inside that is_prime function.

My code looks a lot cleaner and now finds the correct solution in just .5 seconds! What a dramatic increase in efficiency.

DECLARE
i PLS_INTEGER := 1;
prime_counter PLS_INTEGER := 0;
BEGIN
    WHILE prime_counter < 10001
    LOOP
    i:=i+1;
      
        IF EULER_PKG.is_prime(i)
        THEN
            prime_counter := prime_counter + 1;
        END IF;
    END LOOP;

    dbms_output.put_line(i);
END;

--output: 104743

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