UVA 136 - Ugly Number
// UVA 136 - Ugly Number | |
// Problem Definition: http://uva.onlinejudge.org/external/1/136.html | |
open System.Collections.Generic | |
let mutable cache1 = Dictionary<int64,bool>() //Dictionary | |
(* | |
* :()-> () | |
*) | |
let initCache () = | |
cache1 <- Dictionary<int64,bool>() | |
(* | |
* :a:int64 -> b:bool -> bool | |
*) | |
let isFactor (n:int64) (d:int64):bool = n%d = 0L | |
(* | |
* :a:int64 -> b:bool -> bool | |
*) | |
let addToCacheAndRetrunResult n result:bool = | |
if n < 1000000L then | |
cache1.Add(n, result) | |
else | |
() | |
result | |
(* | |
* :a:int64 -> option(bool) | |
*) | |
let getFromCache n = | |
if n < 1000000L then | |
match cache1.TryGetValue(n) with | |
| true, res -> Some(res) | |
| false, _ -> None | |
else | |
None | |
(* | |
* :a:int64 -> b:bool | |
*) | |
let isUglyNumber (x:int64) :bool = | |
let rec checkFactors (n_org:int64) (n:int64) lfactors = | |
match getFromCache n with | |
| Some(x) -> x | |
| None -> | |
match n with | |
| 1L -> addToCacheAndRetrunResult n_org true | |
| _ -> | |
match lfactors with | |
| [] -> addToCacheAndRetrunResult n_org false | |
| d::xs -> | |
if isFactor n d then | |
checkFactors n_org (n/d) lfactors | |
elif n > d then | |
checkFactors n_org n xs | |
else | |
addToCacheAndRetrunResult n_org false | |
checkFactors x x [2L;3L;5L] | |
initCache() // init cache | |
// computing 1500th Ugly Number | |
seq{1L..System.Int64.MaxValue} | |
|> Seq.filter (isUglyNumber) | |
|> Seq.take 1500 | |
|> Seq.last | |
// UVa 136 Problem | |
// Problem Definition: http://uva.onlinejudge.org/external/1/136.html | |
class Main { | |
public static void main(String[] args) { | |
System.out.println("The 1500'th ugly number is 859963392."); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment