Project Euler: Problem 3

euler0003.py

from math import sqrt, ceil

def sieve(numbers):
  primes = []
  while(len(numbers) > 0):
    prime = numbers.pop(0)
    primes.append(prime)
    numbers = [a for a in numbers if a%prime!=0]
  return primes

def largiest_prime_factor(n):
  primes = sieve(range(2, int(ceil(sqrt(n)))))
  while(len(primes) > 0):
    prime = primes.pop()
    if(n%prime==0):
      return prime

print largiest_prime_factor(600851475143)

Euler0003.scala

object Euler0003 {

  def main(args: Array[String]): Unit = {
    println(largiest_prime_factor(600851475143L))
  }

  private def largiest_prime_factor(n: Long) = {
    sieve((2 to Math.sqrt(n).toInt).toList).filter(n%_==0).max
  }

  private def sieve(numbers: List[Int]): List[Int] = {
    sieve(numbers, Nil)
  }

  private def sieve(numbers: List[Int], primes: List[Int]): List[Int] = {
    if(numbers.isEmpty) {
      primes
    } else {
      val h = numbers.head
      sieve(numbers.tail.filter(_%h != 0), h :: primes)
    }
  }
}