Project Euler: Problem 3
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?
http://projecteuler.net/index.php?section=problems&id=3
バカでかい合成数 (600851475143) を分解して得られる最大の素因数を求めよとのこと。
とりあえず Scheme でなんとか書けたが…。後から考えるとバカみたいに無駄が多かったようだ。とりあえず、恥晒しに載っけてみる。
#!/usr/bin/env gosh ;; 最大公約数を求める (実は R5RS にも同じ関数が含まれてたみたい) (define (gcd a b) (if (< a b) (gcd b a) ; a より b が大きかったら入れ替えて再呼び出し (let loop ((a a) (b b)) (let ((r (remainder a b))) ; ユークリッドの互除法 (if (= r 0) b (loop b r)))))) (define (prime-deterministic? n) ; バカ正直に素数かどうか判定する (決定的) (case n [(1) #f] [(2) n] [else (if (even? n) #f (let loop ((i 3) ; minumum odd prime (m (floor->exact (sqrt n)))) (if (<= i m) (if (= (remainder n i) 0) #f ; i で割り切れたら #f (loop (+ i 2) m)) n)))])) ; 全ての i で割り切れなかったとき (use srfi-27) (define (prime-fermat? n) ; フェルマー法で素数を判定する (確率的) (define (fermat? n a) (= (remainder (expt a (- n 1)) n) 1)) ; フェルマーの小定理 (case n [(1) #f] [(2) #t] [else (let test_a ((a (random-integer n))) (if (and (< 1 a n) (= (gcd n a) 1)) ; n と互いに素な乱数 a を求める (fermat? n a) (test_a (random-integer n))))])) ; 乱数が不適切だったら再呼び出し (define prime? prime-fermat?) (define (main args) ;; 約数を集めるためのリスト (define factors '()) ;; 約数に分解して factors に加える (let find-factor ((i 2) (n 600851475143) (lis factors)) (if (<= i n) [begin (if (= (remainder n i) 0) (find-factor (+ i 1) ; (quotient n i) ;; n を i で完全に割り切っておくことで、素数以外の約数をスキップする (let loop ((n n)) ; n を i で完全に割り切る (if (= (remainder n i) 0) (loop (quotient n i)) n)) (cons i lis)) (find-factor (+ i 1) n lis))] (set! factors lis))) ; (print factors) ;; 約数のリストから最大の素数を求める ;; (実際には、find-factor の部分で既に素数のみが選ばれている (let find-prime ((lis factors)) (if (and (pair? lis) (prime? (car lis))) (print (car lis)) (find-prime (cdr lis)))) 0)