Open1
AtCoderで使うテクニック
AntiSatori約数列挙
想定問題
定義
正の整数Nに対してNを割り切れる数、全ての約数を求めること。
例： 40の約数列挙 -> 1, 2, 4, 5, 8, 10, 20, 40
手順
- i = 1の変数を定義する。
- i * i が N よりも大きくなった場合計算を終了する。
- Nがiで割り切れた場合、約数にiを追加する。
- iをNで割った数字がまだ約数に追加されていない場合、約数に追加する。
- iの数に1を足す。
- 2に戻る。
コード
Haskell
solve :: Integer -> Integer -> [Integer] -> [Integer]
solve n m acc
| m ^ (2 :: Integer) > n = acc
| n `mod` m == 0 = solve n (m + 1) (dividable n m) ++ acc
| otherwise = solve n (m + 1) acc
where
dividable i j
| j /= (i `div` j) = [j, i `div` j]
| otherwise = [j]