UVA 136 - Ugly Number

primefactors.fsx

// 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


 

UVa136.java

// 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.");
	}

}