Sunday, April 10, 2011

Project Euler - Problem 3 - Tcl

#The prime factors of 13195 are 5, 7, 13 and 29.
#What is the largest prime factor of the number 600851475143 ?
proc problem3 {} {
 set target_number 600851475143
 set primes [list 2 3]
 set current_number 5

 # let's speed things up a little...
 foreach prime $primes {
  while { ( $target_number % $prime ) == 0  } {
   set target_number [expr ($target_number / $prime) ]
  }
 }

 set finished FALSE
 while { !$finished } {

  set is_prime TRUE
  foreach prime $primes {
   if { ($current_number % $prime) == 0  } {
    set is_prime FALSE
    break
   }
  }

  if { $is_prime } {
   set last_prime $current_number
   lappend primes $last_prime

   while { ( $target_number % $last_prime ) == 0  } {
    set target_number [expr ($target_number / $last_prime) ]
   }
  }

  set finished [expr ($target_number == 1)]

  incr current_number 2
 }

 return [lindex $primes end]
}

# solution-3: 6857

No comments:

Post a Comment