# Thread: PRO NEEDED - int prob

1. ## PRO NEEDED - int prob

hye guys, i have this code below to determine the smallest number that is evenly divisible by all numbers from 1-10 and it works perfectly. but when i try to change the range to 1-20, 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>";                 }                          }     }               } ?> ```

2. 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 1-10
What do you mean by "evenly" divisible?

3. Originally Posted by vectorialpx
For my better understanding, you need to find one number so, you're trying to guess it?
What do you mean by "evenly" divisible?
4 divide by 2 = 2 (no remainder) which means "evenly divisible" google pls.^^

4. UPDATE = maybe its because there's too many loop..any idea too lessen the loop and make the code more simply?

5. 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 1-10
You need this:

PHP Code:
```  <?phpfor ( \$i=1 ;  ; \$i++ ) {        \$haveIt = array();    for( \$j=1; \$j<=10; \$j++ ) {        if( ( \$i % \$j ) == 0 ) {            \$haveIt[] = \$j;        }    }    if( count(\$haveIt) == 10 ) {        echo \$i;        break;    }}?> ```
Of course, "the smallest of all" is 0 (zero) and the next one is 2520

6. 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 non-inclusively, 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";  ```
Note: These scripts, as well as yours, take up a VERY long time to process when you start increasing \$divnum.

7. TQ so much with all your help! GRACIAS! ^^

8. 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.

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•