ホーム

Project Euler¶

• Problem 1
• Problem 2
• Problem 3
• Problem 4
• Problem 5
• Problem 6
• Problem 7
• Problem 8
• Problem 9
• Problem 10

#!r6rs
#!chezscheme

(import (chezscheme))

;;; Problem 1
(define (answer-1)
  (let loop ((n 3) (sum 0))
    (cond
      [(<= 1000 n) sum]
      [(or (zero? (mod n 3)) (zero? (mod n 5)))
       (loop (add1 n) (+ sum n))]
      [else (loop (add1 n) sum)])))

;;; Problem 2
(define (answer-2)
  (let loop ((first 0) (second 1) (result 0))
    (let ((next (+ first second)))
      (cond
        [(< 4000000 next) result]
        [(even? next)
         (loop second next (+ result next))]
        [else (loop second next result)]))))

;;; Problem 3
(define (answer-3)
  (let* ((n 600851475143)
         (check-max (isqrt n)))
    (let loop ((current 3) (rest n) (max-prime 1))
      (cond
        [(< check-max current) max-prime]
        [(zero? (mod rest current))
         (loop current (div rest current) current)]
        [else (loop (+ current 2) rest max-prime)]))))

(define (RotationNumber? num)
  (let* ((num-string (number->string num))
         (str-length (string-length num-string))
         (count (div str-length 2)))
    (let loop ((index 0))
      (cond
        [(<= count index) #t]
        [(equal? (string-ref num-string index) (string-ref num-string (- str-length 1 index)))
         (loop (add1 index))]
        [else #f]))))

;;; Problem 4
(define (answer-4)
  (let loop1 ((num1 100)
              (result 0))
    (if (< 999 num1)
      result
      (let loop2 ((num2 100)
                  (result result))
        (if (< 999 num2)
          (loop1 (add1 num1) result)
          (let ((num (* num1 num2)))
            (if (RotationNumber? num)
              (loop2 (add1 num2) (max result num))
              (loop2 (add1 num2) result))))))))

;;; Problem 5
(define (answer-5)
  (let ((n (* 11 13 15 16 17 19)))
    (let loop ((i n))
      (if (and
            (zero? (mod i 12))
            (zero? (mod i 14))
            (zero? (mod i 18))
            (zero? (mod i 20)))
        i
        (loop (+ i n))))))

;;; Problem 6
(define (answer-6)
  (let loop ((n 1) (sum-all 0) (squared-all 0))
    (if (< 100 n)
      (- (expt sum-all 2) squared-all)
      (loop (add1 n) (+ sum-all n) (+ squared-all (expt n 2))))))

(define (prime? num)
  (if (even? num)
    #f
    (let ((count (isqrt num)))
      (let loop ((check-num 3))
        (cond
          [(< count check-num) #t]
          [(zero? (mod num check-num)) #f]
          [else (loop (+ check-num 2))])))))

;;; Problem 7
(define (answer-7)
  (let loop ((current 3) (count 1) (prime 2))
    (if
      (= 10001 count)
      prime
      (let ((next (+ current 2)))
        (if (prime? current)
          (loop next (add1 count) current)
          (loop next count prime))))))

(define (Problem8-number-string)
  (string-append "73167176531330624919225119674426574742355349194934"
                 "96983520312774506326239578318016984801869478851843"
                 "85861560789112949495459501737958331952853208805511"
                 "12540698747158523863050715693290963295227443043557"
                 "66896648950445244523161731856403098711121722383113"
                 "62229893423380308135336276614282806444486645238749"
                 "30358907296290491560440772390713810515859307960866"
                 "70172427121883998797908792274921901699720888093776"
                 "65727333001053367881220235421809751254540594752243"
                 "52584907711670556013604839586446706324415722155397"
                 "53697817977846174064955149290862569321978468622482"
                 "83972241375657056057490261407972968652414535100474"
                 "82166370484403199890008895243450658541227588666881"
                 "16427171479924442928230863465674813919123162824586"
                 "17866458359124566529476545682848912883142607690042"
                 "24219022671055626321111109370544217506941658960408"
                 "07198403850962455444362981230987879927244284909188"
                 "84580156166097919133875499200524063689912560717606"
                 "05886116467109405077541002256983155200055935729725"
                 "71636269561882670428252483600823257530420752963450"))

;;; Problem 8
(define (answer-8)
  (let* ((p8-num-string (Problem8-number-string))
         (count (- (string-length p8-num-string) 13)))
    (let loop ((index 0) (max-num 0))
      (if (< count index)
        max-num
        (let* ((sub-num (substring p8-num-string index (+ index 13)))
               (char-lis (string->list sub-num))
               (num-lis (map
                          (lambda (char)
                            (- (char->integer char)
                               (char->integer #\0)))
                          char-lis))
               (product-num (fold-left * 1 num-lis)))
          (loop (add1 index) (max max-num product-num)))))))

;;; Problem 9
(define (answer-9)
  (let loop1 ((a 1))
    (if (< 333 a)
      (error "answer-9" "answer-9 was not found!")
      (let loop2 ((b a))
        (if (< 499 b)
          (loop1 (add1 a))
          (let ((c (- 1000 a b)))
            (if (= (+ (expt a 2) (expt b 2)) (expt c 2))
              (* a b c)
              (loop2 (add1 b)))))))))

;;; Problem 10
(define (answer-10)
  (let ((table (make-vector 2000001 #t))
        (count (isqrt 2000000)))
    (vector-set! table 0 #f)
    (vector-set! table 1 #f)

    (let loop1 ((index 2))
      (cond
        [(< count index)
         (let loop2 ((index 0) (result 0))
           (cond
             [(< 2000000 index) result]
             [(vector-ref table index)
              (loop2 (add1 index) (+ result index))]
             [else (loop2 (add1 index) result)]))]
        [(vector-ref table index)
         (let loop3 ((current (* index 2)))
           (cond
             [(< 2000000 current)
              (loop1 (add1 index))]
             [else
               (vector-set! table current #f)
               (loop3 (+ current index))]))]
        [else (loop1 (add1 index))]))))

;(printf "1: ~D~%" (answer-1))
;(printf "2: ~D~%" (answer-2))
;(printf "3: ~D~%" (answer-3))
;(printf "4: ~D~%" (answer-4))
;(printf "5: ~D~%" (answer-5))
;(printf "6: ~D~%" (answer-6))
;(printf "7: ~D~%" (answer-7))
;(printf "8: ~D~%" (answer-8))
;(printf "9: ~D~%" (answer-9))
(printf "10: ~D~%" (answer-10))