Problem 3 「最大の素因数」

13195 の素因数は 5, 7, 13, 29 である.

600851475143 の素因数のうち最大のものを求めよ.

今回のコードの基本的な方針は以下の通りです。

• x = 2 から順に、mod (n , x) = 0 になるまで x += 1
• 割り切れるならば、n /= x , result = xとして繰り返す

数字が大きいので、何か他のアルゴリズムが必要かと思いましたが、素直にやっても一瞬で答えが出ました。

(defparameter *target* 600851475143)

(defun prob3 (n &optional (x 2) (result -1))
    (let* ((is_rem_0 (zerop (rem n x)))
        (max_res (if is_rem_0 x result))
        (next_n (if is_rem_0 (truncate n x) n)))
        (if (= n 1) result
            (prob3 next_n (1+ x) max_res))))

(print (prob3 *target*)) ; 6857

数学ガールの秘密ノート/式とグラフ

posted with amazlet at 14.01.17

結城 浩
ソフトバンククリエイティブ
売り上げランキング: 9,309

Amazon.co.jpで詳細を見る

RECENT POSTS

	Logicool M705mを100均グッズで軽量化する
	どうして自分の欠点ばかりが気になるのか ― 劣等感と所有欲の関係
	日記をつけることの楽しさ ― 記録の効能と醍醐味
	『アイデアの作り方』･･･発想法を定式化した、最もシンプルな本
	『最高の休息法』…「いまここ」の認識と脳疲労
	OmmWriterを使い始めたので、使用感などまとめ。