F# で Project Euler Problem 23
与えられた数を素因数分解して、素因数とその指数とを Map にして返す関数
> let rec get_prime_factor (map:Map<int, int> byref) (n:int) (factor: int) = - if n >= factor then - if n % factor <> 0 then - get_prime_factor &map n (factor + 1) - else - if Map.containsKey factor map then - let n = map.[factor] + 1 - map <- map.Remove factor - map <- (map |> Map.add factor n) - else - map <- (map |> Map.add factor 1) - - get_prime_factor &map (n / factor) factor - ;; val get_prime_factor : byref<Map<int,int>> -> int -> int -> unit
真の約数の和を返す関数
> let sum_of_proper_divisors (n:int):int = - let mutable map:Map<int, int> = Map.empty - get_prime_factor &map n 2 - - if map.IsEmpty then 0 - else - int (map - |> Map.map (fun k t -> (System.Math.Pow(float k,(float t) + 1.0) - 1.0) / float (k - 1)) - |> Map.toList - |> List.map (fun (k, t) -> t) - |> List.reduce(*)) - n - ;; val sum_of_proper_divisors : int -> int
過剰数の List を 作成
> let abundant_list = ( - [12..28123] - |> List.filter(fun n -> (sum_of_proper_divisors n) > n) - ) - ;; val abundant_list : int list = [12; 18; 20; 24; 30; 36; 40; 42; 48; 54; 56; 60; 66; 70; 72; 78; 80; 84; 88; 90; 96; 100; 102; 104; 108; 112; 114; 120; 126; 132; 138; 140; 144; 150; 156; 160; 162; 168; 174; 176; 180; 186; 192; 196; 198; 200; 204; 208; 210; 216; 220; 222; 224; 228; 234; 240; 246; 252; 258; 260; 264; 270; 272; 276; 280; 282; 288; 294; 300; 304; 306; 308; 312; 318; 320; 324; 330; 336; 340; 342; 348; 350; 352; 354; 360; 364; 366; 368; 372; 378; 380; 384; 390; 392; 396; 400; 402; 408; 414; 416; ...] > abundant_list - |> List.length - ;; val it : int = 6965 > abundant_list - |> List.sum - ;; val it : int = 97861532
2つの過剰数の和で書ける数の Set を 作成
> - let abundant_set = - set [ - for x in abundant_list do - for y in (List.filter(fun n -> n >= x) abundant_list) do - let i = x + y - if i <= 28123 then - yield i - ] - ;; val abundant_set : Set<int> = set [24; 30; 32; 36; 38; 40; 42; 44; 48; ...]
2つの過剰数の和で書けない数の総和
> ([1..28123] - |> List.sum) - - (abundant_set - |> Set.toList - |> List.sum) - ;; val it : int = 4179871