guile-project-euler-solutions/naive-prime-test.scm

(library (naive-prime-test)
  (export prime?)

  (import
   (except (rnrs base) let-values)
   (only (guile)
         lambda* λ
         remainder
         inexact->exact))

  (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 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))]))))


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