w3resource logo


Euler Project

Project Euler solution: Smallest Multiple

Secondary Nav

Problem - 5

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

Result : 232792560

Solution in multiple languages

PHP

<?php
$y = 0;
$l = 20;
for ($i = $l; !$y; $i += $l) {
  for ($j = 2; $j < $l; $j++) {
    if ($i % $j == 0) {
      $y = 1;
    }
    else {
      $y = 0;
      break;
    }
  }
  if ($y) {
    echo $i;
    break;
  }
}
?>

Python

def gcd(x,y): return y and gcd(y, x % y) or x
def lcm(x,y): return x * y / gcd(x,y)

n = 1
for i in range(1, 21):
     n = lcm(n, i)
print(n)

Java

import java.math.BigInteger;

public final class eu_p005_sol{

	public static void main(String[] args) {
		System.out.println(new eu_p005_sol().run());
	}
	public String run() {
		BigInteger allLcm = BigInteger.ONE;
		for (int i = 1; i <= 20; i++)
			allLcm = lcm(BigInteger.valueOf(i), allLcm);
		return allLcm.toString();
	}
	private static BigInteger lcm(BigInteger x, BigInteger y) {
		return x.divide(x.gcd(y)).multiply(y);
	}

}

Ruby

#!/usr/bin/env ruby

class Numeric
  def divisibleTo?(x)
    self > 0 and x.downto(1).all? { |i| self % i == 0 }
  end
end

def divisibleTo(x)
  if x < 1
    return false
  elsif x == 1
    return 1
  else
    n = 0
    step = divisibleTo(x-1)
    until n.divisibleTo? x
      n += step
    end
    return n
  end
end

puts divisibleTo(20)

C

#include <stdio.h>

int main()
{

   int zi=1;

   while(1)
   {
      if(zi%11==0 && zi%12==0 && zi%13==0 
         && zi%14==0 && zi%15==0 && zi%16==0 
         && zi%17==0 && zi%18==0 && zi%19==0 
         && zi%20==0) 
      {
          printf("%d\n", zi);
          return 0;
      }

      zi++;
   }

return 0;
}

Go

package main

func main() {
    primes := []int{2, 3, 5, 7, 11, 13, 17, 19}
    result := 1
    var div int
    for i := range primes {
        div = primes[i]
        for div <= 20 {
            div *= primes[i]
        }
        div /= primes[i]
        result *= div
    }
    println(result)
}



Join our Question Answer community to learn and share your programming knowledge.