Problem12が解けたっ

Scheme 30分プログラム

30分プログラム、その275。id:Gemmaさんのアドバイスのおかげでやっと、三角数の約数が解けた。

アドバイスの内容は、

いいかい。約数っていうのは、素因数分解を元に計算するだろ。
でもって、値が小さくて約数を多く持つ数というのは、小さい素因数を数多く持つやつなんだ。
だから、この問題の場合、1-100ぐらいまでの素因数を計算するだけで十分だよ。

というものでした。

そんなんでうまくいく訳が無いじゃないかと、半信半疑で試してみたら、ものすごく速かったです。ちくちょー。
というわけで、ここ数日チャレンジしていたProblem12がやっと解けました。最初に答えを教えてくれたid:selvaggio、素敵なアルゴリズムを教えてくれだid:Gemmaさんには、とてもお世話になりました。また、id:takatoh:20080328:euler012のコードや、id:okagawaさんのコメントも励みになりました。ありがとうございます。

使い方

$ time gosh gemma.scm
(12375 . 76576500)
gosh gemma.scm  0.44s user 0.04s system 84% cpu 0.565 total

環境は、1.8GHz PowerPC G5、512MBでした。源馬アルゴリズムは素敵。

ソースコード

#! /opt/local/bin/gosh
;; -*- mode:scheme; coding:utf-8 -*-
;;
;; gemma.scm -
;;
;; Copyright(C) 2008 by mzp
;; Author: MIZUNO Hiroki / mzpppp at gmail dot com
;; http://howdyworld.org
;;
;; Timestamp: 2008/03/31 23:07:59
;;
;; This program is free software; you can redistribute it and/or
;; modify it under MIT Lincence.
;;

(use util.match)
(use srfi-1)

;;; 1-100までの素数を求めておく
(define (sieve xs)
  "エラトステネスの篩"
  (match xs
    (() '())
    ((x . xs) 
     (cons x (sieve (filter (lambda(n) (not (= (modulo n x) 0))) 
			    xs))))))
;; 100までの素数
(define *prime* (sieve (iota 100 2)))

;;; 約数の個数の計算
;; インチキ素因数分解
(define (prime-factor n)
  (define (f r x y)
    (if (= (modulo x y) 0)
	(f (+ r 1) (quotient x y) y)
	r))
  (filter-map (lambda(p) 
		(and (= (modulo n p) 0) 
		     (cons p (f 0 n p))))
	      *prime*))

(define (count n)
  "約数の個数"
  (fold (lambda(pair n) (* n (+ (cdr pair) 1))) 1 (prime-factor n)))

;; 三角数の約数の計算
(define (tri n)
  "三角数(和の公式)"
  (/ (* n (+ n 1)) 2))

(define (loop n)
  (let1 t (tri n)
    (if (> (count t) 500)
	(cons n t)
	(loop (+ n 1)))))

(define (main _)
  (print (loop 1)))

参考