guile-project-euler-solutions/003.scm

;; https://projecteuler.net/problem=3

;; Largest prime factor

;; Problem 3

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

;; What is the largest prime factor of the number 600851475143 ?


(import
  (except (rnrs base) let-values)
  (only (guile)
        ;; lambda forms
        lambda* λ
        sqrt)
  (srfi srfi-1))


(define even?
  (λ (num)
    (= (remainder num 2) 0)))


(define divides?
  (λ (num div)
    (= (remainder num div) 0)))


;; The biggest potential factor of a number is at maximum
;; its square root. Since we are looking for integer
;; factors, we also floor the square root. If it is even, we
;; substract 1, because even numbers cannot be prime
;; factors, except for 2.
(define biggest-potential-factor
  (λ (num)
    (let ([near-sqrt (inexact->exact (floor (sqrt num)))])
      (cond
       [(= near-sqrt 2) near-sqrt]
       [(even? near-sqrt) (- near-sqrt 1)]
       [else near-sqrt]))))


(define prime?
  (λ (num)
    (if (= num 1)
        #f
        (= (biggest-prime-factor num) 1))))


(define biggest-prime-factor
  (λ (num)
    (let iter ([fac (biggest-potential-factor num)])
      (cond
       ;; Stop looking for factors when reaching 1. This
       ;; prevents the search from going into negative
       ;; numbers towards negative infinity.
       [(= fac 1) 1]
       ;; If the number fac is really a factor of num and it
       ;; is prime, then that is the result.
       [(and (divides? num fac) (prime? fac)) fac]
       ;; 2 is the only even prime factor. If we reach 3, we
       ;; need to decrease by 1 only, so that we also test 2
       ;; as a prime factor.
       [(<= fac 3) (iter (- fac 1))]
       ;; Decrease by 2, to skip even numbers.
       [else (iter (- fac 2))]))))


(simple-format
 (current-output-port)
 "~a\n"
 (biggest-prime-factor 600851475143))