Project Euler Problem 3

Problem 3

02 November 2001

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

Answer: 6857

 

 

Solution in Perl

 

 my $num = 600851475143;
 my $p;
 for ( $p = 2 ; ; $p++ ) {
  while ( $num % $p == 0 ) { $num /= $p; }
  last if ( $num <= 1 );
 }
 print $p;

 

 

Python

 

def problem3():
  num = 600851475143   
  p = 2
  while True:
      while (num % p == 0): num /= p
      if num <= 1: break
      p += 1
  print(p)
(problem3)

 

 

Racket

 

(define (problem3)
  (define num 600851475143)
  (let loop ([p 2])   
    (let loop2 ()
      (when (= 0 (modulo num p)) (set! num (/ num p))(loop2)))
    (cond [(> num 1) (loop (add1 p))]
          [else (display p)])))
(problem3)

; no set!

(define (problem3)

  (let loop ([p 2]

             [num 600851475143])

    (define num2 (let loop ([num num])

                   (if (= 0 (modulo num p)) 

                       (loop (/ num p))

                       num)))

    (cond [(> num2 1)

           (loop (add1 p) num2)]

          [else (display p)])))

; imperative, one loop

#lang racket

(define (problem3)

  (define num 600851475143)

  (define p 2)

  (let loop ()

    (if (zero? (modulo num p))

        (set! num (/ num p))

        (set! p (+ 1 p)))

    (when (> num 1)

      (loop)))

  (displayln p))

(problem3)

Clojure

(defn problem3 []
  (loop [p 2
         num 600851475143]
    (cond (= 1 num) (println p)
          :else
          (cond (zero? (mod num p)) (recur p (quot num p))
                :else (recur (inc p) (long num))))))

 

Go

func problem3() {
 var num int64 = 600851475143
 var p int64
 for p = 2; ; p++ {
  for num%p == 0 {
   num /= p
  }
  if num <= 1 {
   fmt.Println(p)
   break
  }
 }
}

func main() {
 problem3()
}

C++

void problem3() {
  long long num = 600851475143;
  long p;
  for (p = 2; ; p++) {
    while (num%p == 0) {
      num /= p;
    }
    if (num <= 1) {
      printf("%d\n", p);
      break;
    }
  }
}

 

Bash

 

function problem3 {
    num=600851475143
    p=2
    while ((1)); do
        while ((num % p == 0)); do let 'num /= p'; done
        if ((num <= 1)); then break; fi
        let 'p++'
    done
    echo $p
}

problem3

Javascript

var num = 600851475143;
for (var p = 2; ; p++) {
 while (num%p == 0) num /= p;
 if (num <= 1) break;
}
p

 

 

Haskell

 

maxPrimeFactor n = factor n 1 2
  where
    factor n p i
      | n == 1 = p
      | (mod n i) == 0 = factor (div n i) i i
      | otherwise = factor n p (i+1)

main = do
  print $ maxPrimeFactor 600851475143

 

* newLISP

 

(set 'num 600851475143)
(set 'p 1)
(while (> num 1)
  (++ p)
  (while (= 0 (% num p)) (set 'num (/ num p))))
(println p)

 

Emacs Lisp

(set 'num 600851475143)
(set 'p 1)
(while (> num 1)
  (setq p (1+ p))
  (while (zerop (% num p)) (set 'num (/ num p))))
(print p)

Common Lisp

(let ((num 600851475143)
      (p 1))
  (loop while (> num 1) do
       (setq p (1+ p))
       (loop while (zerop (mod num p)) do (setq num (/ num p))))
  (print p))

 

Arc

 

(= num 600851475143)
(= p 1)
(while (> num 1)
  (++ p)
  (while (is 0 (mod num p)) (= num (/ num p))))
(prn p)