Tags: data dictionary

Project Euler Q3 with Mysql

By admin on Sep 7, 2009 | In Formula 1 - More advanced stuff, Showroom - Examples of Mysql usage | Send feedback »

Here is the question set for us this time from The Euler Project

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

What is the largest prime factor of the number 600851475143

In Mysql you can calulate prime numbers using a "numbers" table eg:

Code:

select * from t500 a where a.id != 1
and not exists
(select * from t500 b where b.id !=1  
and b.id < a.id and mod(a.id,b.id) = 0)

But this is probably not efficient or realistic for larger numbers (and we are probably looking at big numbers in this exercise).
Another way to approach this is to work out the smallest divisor of the original number starting from 2, divide out that number, and again (starting from 2) find the next smallest divisor (ie bigger than or equal to the previous result) of that new number. Carry on doing this until we can go no further and we should end up with the largest prime factor (as for instance a factor of 8 would be broken down by 2 twice). I hope the following Mysql code makes sense; we increment the variable var1 by 1 each time and test (via the mod function) whether it's a factor of the variable bignuma. If it is, we divide out var1 to get a smaller bignuma, and start incrementing var1 again from 2.

Code:

set @var1=2;
set @varreset=2;
set @bignuma= 600851475143;
 
*** a1factor displays prime factors in bignuma ***
select a1factor from
(select  
case when mod(@bignuma,@var1) = 0
   then @var1:=@varreset
   else @var1:=@var1+1  end as a1factor,
case when mod(@bignuma,@var1) = 0
   then @bignuma:=@bignuma/@var1
   end as new_factor
 from orders where @var1<@bignuma ) tmp
where new_factor is not null
order by a1factor desc;
 
# This produces the values: 6857, 1471, 839, 71

In my three blog entries on iterating through numbers I've used a table that I've already created and populated in my database (in this case it's called orders). Although it's relatively straightforward to create a table yourself with lots of rows, there are system tables you can use for this purpose. I recently found this on the web - openark blog mysql - a very good read. If they are installed you can use rows from mysql.help_topic, otherwise the author suggests you can use tables from the data dictionary INFORMATION_SCHEMA instead like COLLATIONS or COLUMNS. You do need to check first that there are enough rows to suit your requirement though. As this method can also be slow I would recommend that you create a table with the required number of rows for iteration purposes where possible. Here's one way you can populate a table with a range of numbers in Mysql ( taken from a question on Stack overflow by a user known as PittsburghDBA). This generates 1000 rows (from 0 to 999) using the combination of using a cross join method with the UNION keyword, but you can always adapt it to suit yourself.

Code:

INSERT INTO
    myTable
    (
    nr
    )
SELECT
    SEQ.SeqValue
FROM
(
SELECT
    (HUNDREDS.SeqValue + TENS.SeqValue + ONES.SeqValue) SeqValue
FROM
    (
    SELECT 0  SeqValue
    UNION ALL
    SELECT 1 SeqValue
    UNION ALL
    SELECT 2 SeqValue
    UNION ALL
    SELECT 3 SeqValue
    UNION ALL
    SELECT 4 SeqValue
    UNION ALL
    SELECT 5 SeqValue
    UNION ALL
    SELECT 6 SeqValue
    UNION ALL
    SELECT 7 SeqValue
    UNION ALL
    SELECT 8 SeqValue
    UNION ALL
    SELECT 9 SeqValue
    ) ONES
CROSS JOIN
    (
    SELECT 0 SeqValue
    UNION ALL
    SELECT 10 SeqValue
    UNION ALL
    SELECT 20 SeqValue
    UNION ALL
    SELECT 30 SeqValue
    UNION ALL
    SELECT 40 SeqValue
    UNION ALL
    SELECT 50 SeqValue
    UNION ALL
    SELECT 60 SeqValue
    UNION ALL
    SELECT 70 SeqValue
    UNION ALL
    SELECT 80 SeqValue
    UNION ALL
    SELECT 90 SeqValue
    ) TENS
CROSS JOIN
    (
    SELECT 0 SeqValue
    UNION ALL
    SELECT 100 SeqValue
    UNION ALL
    SELECT 200 SeqValue
    UNION ALL
    SELECT 300 SeqValue
    UNION ALL
    SELECT 400 SeqValue
    UNION ALL
    SELECT 500 SeqValue
    UNION ALL
    SELECT 600 SeqValue
    UNION ALL
    SELECT 700 SeqValue
    UNION ALL
    SELECT 800 SeqValue
    UNION ALL
    SELECT 900 SeqValue
    ) HUNDREDS
) SEQ


I hope in the last 3 blog entries I've given some idea on how to approach solving the problems in the Euler Project with Mysql. Although I'll continue looking at the problems myself, I won't be publishing most of the solutions here, so it's up to you if you continue or not (with or without Mysql). Good luck!

Tags: data dictionary, project euler, union, variables