SitePoint Sponsor 

User Tag List
Results 1 to 8 of 8
Thread: PRO NEEDED  int prob

Mar 7, 2013, 23:27 #1
 Join Date
 Jan 2013
 Posts
 110
 Mentioned
 0 Post(s)
 Tagged
 0 Thread(s)
PRO NEEDED  int prob
hye guys, i have this code below to determine the smallest number that is evenly divisible by all numbers from 110 and it works perfectly. but when i try to change the range to 120, things got weird. the ans should be 232792560 and when i try to change the initial $k to 999999999 for bigger scope,but i can't get the answer which i SUPPOSE can get the answer as 999999999 > 232792560. When i tried changing $k to 233333333 then only i get the answer 232792560. WHY IS THAT? help me pls
PHP Code:<?
for ($k=9999; $k >= 1 ; $k)
{
for ($c=0,$i=1; $i <= 10 ; $i++)
{
if ($k%$i == 0)
{
$c++;
if ($c == 10)
{
echo $k."<br>";
}
}
}
}
?>

Mar 8, 2013, 02:55 #2
 Join Date
 Dec 2012
 Location
 Bucharest
 Posts
 247
 Mentioned
 8 Post(s)
 Tagged
 0 Thread(s)
For my better understanding, you need to find one number so, you're trying to guess it?
smallest number that is evenly divisible by all numbers from 110

Mar 8, 2013, 05:05 #3
 Join Date
 Jan 2013
 Posts
 110
 Mentioned
 0 Post(s)
 Tagged
 0 Thread(s)

Mar 8, 2013, 05:36 #4
 Join Date
 Jan 2013
 Posts
 110
 Mentioned
 0 Post(s)
 Tagged
 0 Thread(s)
UPDATE = maybe its because there's too many loop..any idea too lessen the loop and make the code more simply?

Mar 11, 2013, 03:22 #5
 Join Date
 Dec 2012
 Location
 Bucharest
 Posts
 247
 Mentioned
 8 Post(s)
 Tagged
 0 Thread(s)
I know what "evenly" means but I don't understand your logic.
To get:the smallest number that is evenly divisible by all numbers from 110
PHP Code:<?php
for ( $i=1 ; ; $i++ ) {
$haveIt = array();
for( $j=1; $j<=10; $j++ ) {
if( ( $i % $j ) == 0 ) {
$haveIt[] = $j;
}
}
if( count($haveIt) == 10 ) {
echo $i;
break;
}
}
?>

Mar 11, 2013, 07:27 #6
 Join Date
 Feb 2006
 Location
 Atlanta, GA, USA
 Posts
 3,748
 Mentioned
 69 Post(s)
 Tagged
 0 Thread(s)
You want the SMALLEST number. So start from the bottom and work upwards. Your script starts at the top and works down; it will find the LARGEST number.
2 input variables; $max and $divnum. Find the smallest integer less than $max which is divisible by all integers 2 through $divnum inclusive (every integer is divisible by 1).
FACT: No number between 2 and $divnum is divisible by all numbers between 2 and$divnum. So we can safely exclude everything until then.
Geeky Math Explanation: (Forall X such that X < Y, X (the seeking value) and Y (the divisibility number) in the set of positive nonzero integers, 0 < X/Y < 1. As the definition of a divisible integer would be that X is divisible by Y if there exists an integer M such that X = MY, rewritten as M = X/Y. X/Y has been defined as between 0 and 1 noninclusively, and so the set of values of M is empty.)
Even more Geeky Math Explanation: You can define $max as $divnum!, because the factorialization of a number is by definition divisible by all positive integers less than it, and thus is the first guaranteed number as such. (The rest would be an integer multiple thereof)
PHP Code:for ($x = $divnum; $x <= $max; $x++) {
$go = true;
$y = 2;
while( $go && $y <= $divnum) {
$go = (($x % $y) == 0);
$y++;
}
if($go) { break; }
}
echo ($go) ? $x : "Not Found";
Never grow up. The instant you do, you lose all ability to imagine great things, for fear of reality crashing in.

Mar 11, 2013, 09:36 #7
 Join Date
 Jan 2013
 Posts
 110
 Mentioned
 0 Post(s)
 Tagged
 0 Thread(s)
TQ so much with all your help! GRACIAS! ^^

Mar 13, 2013, 06:58 #8
 Join Date
 Feb 2006
 Location
 Atlanta, GA, USA
 Posts
 3,748
 Mentioned
 69 Post(s)
 Tagged
 0 Thread(s)
I thought about this a bit more. There is a LOT faster way to come up with this number.
It works on the mathematical principles of factorization.
Here is a definition of how to find the number you seek; see if you can code it.
The Smallest Number divisible by every number 1..X can be defined as the product of all prime factors of the numbers in 1..X raised to the power of the maximum occurance of that factor.
(So if X was 4, 2's prime factor is 2^1, 3's prime factor is 3^1, 4's prime factors are 2^2; thus your number is 2^2 * 3^1, or 12.)
It will be MUCH faster to find the factors and then multiply them together; what took my original script 130.15 seconds to find the smallest number with X = 20, it took this revised theory's script 1 milisecond to calculate.Never grow up. The instant you do, you lose all ability to imagine great things, for fear of reality crashing in.
Bookmarks