CODEWITHSUNDEEP
phpalgorithm
user3319461
user3319461

Reputation:

how can this algorithm be optimized

I am trying to find the smallest positive number that is evenly divisible by all of the numbers from 1 to 20 and here is the code:

$num = 2520;
$x = 1;

while($x < 21){
    if($num % $x == 0){
        $x++;
    }else{
        $num += 20;
        $x = 1;
    }
}

echo $num;

it gives a proper output in less than 1 minute. Is this execution time bad in the professional world? any way to optimize this?

P.S. I started from 2520 because it is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

Upvotes: 1

Views: 98

Answers (3)

Spektre
Spektre

Reputation: 51835

use modified Sieve of Eratosthenes for massive speed up

1.int ix[20]={1,2,3,4,...20};

2.now write a loop

  • where you will increment all ix[i]+=i+1; where i=<0;18>
  • while ix[i]>=ix[19]
  • if at the end all ix[i] are the same then its contens is the result so stop/return whatever

3.if not then increment also ix[19]+=20;

  • and continue with the loop on bullet 2

[notes]

  • can be easily changed for searing for divisible by any numbers not just divisible by 1..20

Upvotes: 0

Erik J. Sturcke
Erik J. Sturcke

Reputation: 178

This sounds like Project Euler's Problem 5.

What we are finding here is the least common multiple of numbers 1 to 20. You can find this with help form the greatest common divisor:

function gcd($a, $b) {
    if ($a == 0) return $b;
    return gcd($b % $a, $a);
}

function lcm($a, $b) {
    return $a * $b / gcd($a, $b);
}

function smallestDiv($n) {
    $div = 1;
    for ($i = 1; $i <= $n; $i++) {
        $div = lcm($div, $i);
    }
    return $div;
}

echo smallestDiv(20);

Pardon my PHP. It's been a while since I have written any.

Note that we can also find the answer via prime factorization of each of the numbers and looking for the largest exponents as described here and in Kode Charlie's answer:

 2 = 2
 3 = 3
 4 = 2²
 5 = 5
 6 = 2 × 3
 7 = 7
 8 = 2³
 9 = 3²
10 = 2 × 5
11 = 11
12 = 2² × 3
13 = 13
14 = 2 × 7
15 = 3 × 5
16 = 2⁴
17 = 17
18 = 2 × 3²
19 = 19
20 = 2² × 5

lcm(1,2,…20) = 2⁴ × 3² × 5 × 7 × 11 × 13 × 17 × 19 = 232,792,560

Upvotes: 0

Kode Charlie
Kode Charlie

Reputation: 1479

Suggestion: find the primes of all integers in [1,20].

Eg, we have the primes {2,3,5,7,11,13,17,19}. So, if the solution is divisible by all integers in [1,20], then surely it is divisible by each element in this list of primes. So, at a minimum, our solution is >= 2*3*5*7*11*13*17*19, right?

Now the problem is how clever we can be about constructing candidate solutions larger than that number. Well, let's first see how much of the solution is done...

Is 2*3*5*7*11*13*17*19 divisible by 4? No. So, let's multiple by 2 to get 2*2*3*5*7*11*13*17*19, which surely is divisible by 2*2...

Is 2*2*3*5*7*11*13*17*19 divisible by 6? Yes.

Is 2*2*3*5*7*11*13*17*19 divisible by 8? ....

You get the picture. While I am not sure, I believe this approach will result in the right answer -- ie, the smallest integer divisible by each integer in [1,20].

Upvotes: 1

Related Questions