Sunday, April 10, 2011

Project Euler - Problem 5 - Tcl

#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?
proc problem5 {} {
 # REMARK: Runs forever :)
 set dividers [list ]
 for { set idx 20 } { $idx >= 2 } {incr idx -1} {
  lappend dividers $idx
 }
 set largest_divider 20

 set divisible FALSE
 set current_number 20

 while { ! $divisible } {
  incr current_number $largest_divider

  set divisible TRUE
  foreach divider $dividers {
   if {( $current_number % $divider ) != 0} {
    set divisible FALSE
    break
   }
  }
 }

 foreach divider $dividers {
  puts "$current_number / $divider = [expr $current_number / $divider] + [expr $current_number % $divider]/$divider"
 }

 return $current_number
}

#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?
proc problem5-v2 {} {
 # REMARK: will get me very fast to the wanted number
 set largest_divider 1
 set dividers [list ]

 for { set idx 20 } { $idx >= 2 } {incr idx -1} {
  set largest_divider [expr $largest_divider * $idx]
  lappend dividers $idx
 }
 puts "largest divider=$largest_divider"

 foreach divider $dividers {
  while {( $largest_divider % $divider ) == 0} {
   set largest_divider [expr $largest_divider / $divider]
  }

  set largest_divider [expr $largest_divider * $divider]
 }

 foreach divider $dividers {
  puts "$largest_divider / $divider = [expr $largest_divider / $divider] + [expr $largest_divider % $divider]/$divider"
 }

 return $largest_divider  ;# == 9699690
}

proc problem5-v3 {} {
 # REMARK: Based on v2, all we need is to correct the results manually.
 set largest_divider [expr 9699690*4*3*2]

 set dividers [list ]
 
  for { set idx 20 } { $idx >= 2 } {incr idx -1} {
   lappend dividers $idx
  }
 
 
 foreach divider $dividers {
  puts "$largest_divider / $divider = [expr $largest_divider / $divider] + [expr $largest_divider % $divider]/$divider"
 }

}

# solution-4: 232792560

No comments:

Post a Comment