Step-by-Step Guide: Finding Prime Numbers with MySQL

By /
Step-by-Step Guide: Finding Prime Numbers with SQL

The Task

Write a query to print all prime numbers less than or equal to 1000. Print your result on a single line, and use the ampersand (&) character as your separator (instead of a space).

For example, the output for all prime numbers ≤10 would be:

2&3&5&7

Let’s solve it with MySQL

Sure! Let’s break down the SQL query step-by-step and explain each part in detail.

Step-by-Step Explanation

Generate Numbers from 1 to 1000:

  • To generate a list of numbers from 1 to 1000, we use a sequence of UNION ALL statements along with a variable @row to create a sequence.

SELECT @row := @row + 1 AS n
FROM 
      (SELECT 0 UNION ALL SELECT 1 UNION ALL SELECT 2 UNION ALL SELECT 3 UNION ALL SELECT 4 UNION ALL SELECT 5 UNION ALL SELECT 6 UNION ALL SELECT 7 UNION ALL SELECT 8 UNION ALL SELECT 9) t1,
      (SELECT 0 UNION ALL SELECT 1 UNION ALL SELECT 2 UNION ALL SELECT 3 UNION ALL SELECT 4 UNION ALL SELECT 5 UNION ALL SELECT 6 UNION ALL SELECT 7 UNION ALL SELECT 8 UNION ALL SELECT 9) t2,
      (SELECT 0 UNION ALL SELECT 1 UNION ALL SELECT 2 UNION ALL SELECT 3 UNION ALL SELECT 4 UNION ALL SELECT 5 UNION ALL SELECT 6 UNION ALL SELECT 7 UNION ALL SELECT 8 UNION ALL SELECT 9) t3,
      (SELECT @row := -1) t0

We are essentially using nested queries to generate a Cartesian product which creates a large number of rows, and by initializing a variable @row, we can sequentially number these rows.

Filter Out Non-Primes:

  • To determine if a number is prime, we need to check if it has any divisors other than 1 and itself.A prime number n should not be divisible by any number from 2 up to the square root of n.

WHERE NOT EXISTS (
    SELECT 1
    FROM (
        SELECT 2 AS factor UNION SELECT 3 UNION SELECT 4 UNION SELECT 5 UNION SELECT 6 UNION SELECT 7 UNION SELECT 8 UNION SELECT 9 UNION SELECT 10 UNION SELECT 11 UNION SELECT 12 UNION SELECT 13 UNION SELECT 14 UNION SELECT 15 UNION SELECT 16 UNION SELECT 17 UNION SELECT 18 UNION SELECT 19 UNION SELECT 20 UNION SELECT 21 UNION SELECT 22 UNION SELECT 23 UNION SELECT 24 UNION SELECT 25 UNION SELECT 26 UNION SELECT 27 UNION SELECT 28 UNION SELECT 29 UNION SELECT 30 UNION SELECT 31
    ) factors
    WHERE n % factor = 0 AND n != factor
)

We check each number n to see if there exists any factor (2, 3, 4, …, 31) that divides n exactly (n % factor = 0), excluding n itself. If such a factor exists, n is not prime.

Concatenate Prime Numbers:

  • After filtering out the non-prime numbers, we use the GROUP_CONCAT function to concatenate all the prime numbers into a single string separated by &.

SELECT GROUP_CONCAT(prime SEPARATOR '&') AS primes
FROM (
    SELECT n AS prime
    FROM ...
) prime_numbers;

GROUP_CONCAT takes all the results of the subquery and joins them into one string, using the & character as the separator.

Full Query with Comments

Here is the entire query with detailed comments for each part:

-- Initialize variables
SELECT GROUP_CONCAT(prime SEPARATOR '&') AS primes
FROM (
    -- Select the numbers from 1 to 1000
    SELECT n AS prime
    FROM (
        SELECT n
        FROM (SELECT @row := @row + 1 AS n FROM 
              -- Creating a large set of rows using UNION ALL
              (SELECT 0 UNION ALL SELECT 1 UNION ALL SELECT 2 UNION ALL SELECT 3 UNION ALL SELECT 4 UNION ALL SELECT 5 UNION ALL SELECT 6 UNION ALL SELECT 7 UNION ALL SELECT 8 UNION ALL SELECT 9) t1,
              (SELECT 0 UNION ALL SELECT 1 UNION ALL SELECT 2 UNION ALL SELECT 3 UNION ALL SELECT 4 UNION ALL SELECT 5 UNION ALL SELECT 6 UNION ALL SELECT 7 UNION ALL SELECT 8 UNION ALL SELECT 9) t2,
              (SELECT 0 UNION ALL SELECT 1 UNION ALL SELECT 2 UNION ALL SELECT 3 UNION ALL SELECT 4 UNION ALL SELECT 5 UNION ALL SELECT 6 UNION ALL SELECT 7 UNION ALL SELECT 8 UNION ALL SELECT 9) t3,
              -- Initializing the row variable
              (SELECT @row := -1) t0
        ) numbers
        WHERE n > 1
    ) num
    -- Filter out the non-prime numbers
    WHERE NOT EXISTS (
        SELECT 1
        FROM (
            SELECT 2 AS factor UNION SELECT 3 UNION SELECT 4 UNION SELECT 5 UNION SELECT 6 UNION SELECT 7 UNION SELECT 8 UNION SELECT 9 UNION SELECT 10 UNION SELECT 11 UNION SELECT 12 UNION SELECT 13 UNION SELECT 14 UNION SELECT 15 UNION SELECT 16 UNION SELECT 17 UNION SELECT 18 UNION SELECT 19 UNION SELECT 20 UNION SELECT 21 UNION SELECT 22 UNION SELECT 23 UNION SELECT 24 UNION SELECT 25 UNION SELECT 26 UNION SELECT 27 UNION SELECT 28 UNION SELECT 29 UNION SELECT 30 UNION SELECT 31
        ) factors
        WHERE n % factor = 0 AND n != factor
    )
) prime_numbers;

Summary

  • Step 1: Generate a sequence of numbers from 1 to 1000 using UNION ALL and a variable.
  • Step 2: Filter out non-prime numbers by checking for divisors.
  • Step 3: Concatenate the resulting prime numbers into a single string separated by &.

This approach ensures that we correctly identify and list all prime numbers less than or equal to 1000, formatted as specified.

The expected output should look something like this:

2&3&5&7&11&13&17&19&23&29&31&37&41&43&47&53&59&61&67&71&73&79&83&89&97&101&103&107&109&113&127&131&137&139&149&151&157&163&167&173&179&181&191&193&197&199&211&223&227&229&233&239&241&251&257&263&269&271&277&281&283&293&307&311&313&317&331&337&347&349&353&359&367&373&379&383&389&397&401&409&419&421&431&433&439&443&449&457&461&463&467&479&487&491&499&503&509&521&523&541&547&557&563&569&571&577&587&593&599&601&607&613&617&619&631&641&643&647&653&659&661&673&677&683&691&701&709&719&727&733&739&743&751&757&761&769&773&787&797&809&811&821&823&827&829&839&853&857&859&863&877&881&883&887&907&911&919&929&937&941&947&953&967&971&977&983&991&997

Related Posts

Scroll to Top