PDA

View Full Version : PHP - Euler #5 Problems :(



Moonbat
07-15-2008, 04:47 PM
First off, here's the problem: "What is the smallest number divisible by each of the numbers * to 20?"

I went with the good ol' brute-force method. But after trying every combination of loops, if statements, etc. I can't get a working solution. Here's what I'm using so far.

<?php

set_time_limit(0);
for ($i=0; $i<=*000000; $i++) {
if (($i &#*7; 2) == 0 && ($i % *) == 0 && ($i % 4) == 0 && ($i % 5) == 0 && ($i % 6) == 0 && ($i % 7) == 0 && ($i % 8) == 0 && ($i % *) == 0 && ($i % *0) == 0 && ($i % **) == 0 && ($i % *2) == 0 && ($i % **) == 0 && ($i % *4) == 0 && ($i % *5) == 0 && ($i % *6) == 0 && ($i % *7) == 0 && ($i % *8) == 0 && ($i % **) == 0 && ($i % 20) == 0) {
echo "<h2>" . $i . "</h2>";
echo "<br>";
} else {
echo "";
}
}

?>
Even though my for loop goes up to *,000,000, be assured I've tried up to 5,000,000. I doubt the smallest number that can be divided evenly by *-20 is any bigger than *,000,000. What is wrong with my script?

~~smart~fool~~
07-16-2008, 12:06 AM
Sorry to hax you but

Rather than doing **.6M iterations why not:

- find prime factors of each number - you nearly did this

- take the smallest necessary collection of those prime numbers (the highest power of each prime)

- multiply them up

And bingo: you have:

2*2*2*2 * *** * 5 * 7 * ** * ** * *7 * ** = 2*2,7*2,560

Finding prime factors is easy, and I think this would be more scalable

Moonbat
07-16-2008, 10:52 AM
Thanks for the idea. I'll try to get it working :D

~~smart~fool~~
07-18-2008, 01:06 PM
The Principle of Parsimony - It is pointless to do with more what is done with less