Project Euler(with Scheme) Problem 6〜10 - プログラミングを上達させたい

引き続きやってます。
はじめると楽しいですね。
まだ躓いていないから、というのもありますが・・・

Problem 6

(define (solve n)
  (define (sub now wa p2wa)
    (if (> now n) (abs (- (* wa wa) p2wa))
        (sub (+ now 1) (+ wa now) (+ p2wa (* now now)))))
  (sub 1 0 0))

;(solve 10)
(solve 100)

和の2乗と 2乗の和を1つの関数で求められるように書きました。

Problem 7

(define (prime? n)
  (define (sub now)
    (cond ((> (* now now) n) #t)
          ((= 0 (modulo n now)) #f)
          (#t (sub (+ now 1)))))
  (if (<= n 1) #f (sub 2)))

(define (solve n)
  (define (sub now count)
    (if (prime? now)
        (if (= count n) now
            (sub (+ now 1) (+ count 1)))
        (sub (+ now 1) count)))
  (sub 2 1))

;(solve 6)
(solve 10001)

前の記事ではO(n)で実装していた(prime? n)を、O(root(n))に改良しました。

Problem 8

(define (toint char) (- (char->integer char) 48))
(define (seki string)
  (define (sub ind seki)
    (if (= ind (string-length string)) seki
        (sub (+ ind 1) (* seki (toint (string-ref string ind))))))
  (sub 0 1))
;(seki "1230")

(define (solve string)
  (define (sub nowstart maxnum)
    (if (>= (+ nowstart 12) 1000) maxnum
        (sub (+ nowstart 1) (max maxnum (seki (substring string nowstart (+ nowstart 13)))))))
  (sub 0 0))

(solve "7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450")

1000桁の数は数字ではなく文字列として扱いました。"0"の扱いが面倒だったので。

Problem 9

(define (solve a b)
  (if (= (+ (* a a) (* b b)) (let ((c (- 1000 (+ a b)))) (* c c))) (* a b (- 1000 (+ a b)))
      (if (> a 500)
          (solve 1 (+ b 1))
          (solve (+ a 1) b))))
(solve 1 1)

なんか解くためだけのコードで、キレイさとかを考えずに書いている。これでいいのか？人生

Problem 10

(define (prime? n)
  (define (sub now)
    (cond ((> (* now now) n) #t)
          ((= 0 (modulo n now)) #f)
          (#t (sub (+ now 1)))))
  (if (<= n 1) #f (sub 2)))

(define (solve n)
  (define (sub now sum)
    (if (<= now 0) sum
        (sub (- now 1) (+ sum (if (prime? now) now 0)))))
  (sub n 0))

;(solve 10)
(solve 2000000)

解けはしたものの、計算に数十秒かかった。O(n * root(n))でn = 2000000なので、確かにAtCoderではアウトな計算量。
でも、エラトステネスのふるいとか使っても同じくらいかかりますよね？アレ？と思ったのでそっちの解法も書いてみる。

(define (generate n)
  (define (sub now)
    (if (> now n) '()
        (cons now (sub (+ now 1)))))
  (sub 2))

(define (modulo-filter n list)
  (if (null? list) '()
      (if (= (modulo (car list) n) 0)
          (modulo-filter n (cdr list))
          (cons (car list) (modulo-filter n (cdr list))))))

(define (solve n)
  (define (sub list sum)
    (if (null? list) sum
        (let ((carnum (car list)))
          (sub (modulo-filter carnum (cdr list)) (+ sum carnum)))))
  (sub (generate n) 0))

;(solve 10)
(solve 2000000)

実行すると、こっちの方が圧倒的に時間がかかった(数分では計算完了しなかった)。
というかこれは(素数の密度とかはよく分からないが)、計算量はO(n^2)になってしまっている？ようなのでそりゃそうか。

どうなんでしょ、この問題の高速化はもっとできるんだろうか。

今回は一旦ここまで。先の問題を見てみると、解けるけどめんどくさい(数学的にもアルゴリズム的にも簡単で、書くのが面倒)というものが続きそうだった。
ただ、それをちゃんとSchemeで書くのは意味のあることなので、なんとかモチベーションを保っていきたいところ。
以上です。