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!