SitePoint Sponsor

User Tag List

Results 1 to 8 of 8
  1. #1
    SitePoint Zealot
    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 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 >= ;  $k--)
     {
        for (
    $c=0,$i=1$i <= 10 $i++)
        {
                if (
    $k%$i == 0)
            {
                
    $c++;
                
                    if (
    $c == 10)
                    {    
                    echo 
    $k."<br>";
                    }
                    
            }
        }
                 
    }
    ?>

  2. #2
    SitePoint Addict bronze trophy vectorialpx's Avatar
    Join Date
    Dec 2012
    Location
    Bucharest
    Posts
    219
    Mentioned
    7 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 1-10
    What do you mean by "evenly" divisible?

  3. #3
    SitePoint Zealot
    Join Date
    Jan 2013
    Posts
    110
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Quote Originally Posted by vectorialpx View Post
    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. #4
    SitePoint Zealot
    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?

  5. #5
    SitePoint Addict bronze trophy vectorialpx's Avatar
    Join Date
    Dec 2012
    Location
    Bucharest
    Posts
    219
    Mentioned
    7 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 1-10
    You need this:

    PHP Code:
     <?php

    for ( $i=;  ; $i++ ) {
        
        
    $haveIt = array();
        for( 
    $j=1$j<=10$j++ ) {
            if( ( 
    $i $j ) == ) {
                
    $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. #6
    Keeper of the SFL StarLion's Avatar
    Join Date
    Feb 2006
    Location
    Atlanta, GA, USA
    Posts
    3,747
    Mentioned
    65 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 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.
    Never grow up. The instant you do, you lose all ability to imagine great things, for fear of reality crashing in.

  7. #7
    SitePoint Zealot
    Join Date
    Jan 2013
    Posts
    110
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    TQ so much with all your help! GRACIAS! ^^

  8. #8
    Keeper of the SFL StarLion's Avatar
    Join Date
    Feb 2006
    Location
    Atlanta, GA, USA
    Posts
    3,747
    Mentioned
    65 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

Posting Permissions

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