Euler-sol-5

From ProgSoc Wiki

Jump to: navigation, search

Contents

Solutions for Problem 5

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

Perl by Stryker

Runtime: ??ms

 #!/usr/bin/perl
 # http://projecteuler.net/index.php?section=problems&id=5
 # written in about 10 minutes.
 # no optimisations
 #
 $x=21;
 while ($x)
 {
 $a=$x%11;
  if($a==0){ $b=$x%12;
    if($b==0){ $c=$x%13;
      if($c==0){ $d=$x%14;
        if($d==0){ $e=$x%15;
          if($e==0){ $f=$x%16;
            if($f==0){ $g=$x%17;
              if($g==0){ $h=$x%18;
                if($h==0){ $i=$x%19;
                  if($i==0){ $j=$x%20;
                    if($j==0){ print $x."\n";
                      exit;
   } } } } } } } } } }
   $x++;
 }

C++ by SanguineV

Runtime: 7ms

// Many numbers can be excluded as any factors will also be factors of other numbers in the range 1-20
// Number: covered by
// 24 : 2,3,4,6,8,12
// Primes: 2,3,5,7,11,13,17,19
// Intersect these two and they cover:
// 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20
#include <iostream>
using namespace std;

int main(char* argv, int argc) {
  long res = 24*2*3*5*7*11*13*17*19;
  cout << res << endl;
}


Python by Althalus

Forgot to note the runtime.

import time
start_time = time.time()

start=20
done=0


while done==0:
	done=1
	i=2
#Starting at 20 and going up by 20. Therefore, will be divisible by 20, and subsequently, factors of 20. (10, 5, 4, 2)
	start=start+20
	if start%19 != 0: #Prime.
		done=0
	if start%17 != 0: #Prime.
		done=0
	if start%18 != 0: #Also divisibly by 9, 6, 3
		done=0
	if start%16 != 0: #Also divisibly by 8
		done=0
	if start%15 != 0:
		done=0
	if start%14 != 0: #ALso divisible by 4.
		done=0
	if start%13 != 0: #Prime
		done=0
	if start%12 != 0:
		done=0
	if start%11 != 0: #Prime
		done=0
	
print(start)
run_time = time.time() - start_time
print ('Run time: ', run_time, ' seconds',)

Excel VBA by mmaster

1 minute 38 seconds

   Sub ProblemFive()
   Dim max
   Dim MagicNumber As Integer
   MagicNumber = 20
   Dim k
   
   max = 1
   For i = 1 To MagicNumber
       max = max * i
   Next i
   
   For i = MagicNumber + 1 To max
       For j = 2 To MagicNumber
           k = 0
           If i Mod j <> 0 Then
               Exit For
           End If
           k = j
       Next j
       If k = MagicNumber Then
           MsgBox i
           Exit Sub
       End If
   Next i
   
   End Sub

Haskell by SanguineV

Runtime: 5 ms

main = print (head (filter (\x -> all (\z -> mod x z == 0) [12,16,18,20])
                           [2*3*5*7*11*13*17*19*i | i <- [1..]]))

Javascript by ctd

Runtime: 7.9 seconds

var i = 0, even = false;
while (!even) {
	i++;
	even = evenlyDivides(i, 20);
}
console.log(i);

function evenlyDivides(num, den) {
	if (den == 0) return true;
	if (num % den == 0)
		return evenlyDivides(num, den-1);
	else
		return false;
}
Personal tools