I was exploring Jupyter notebooks , that combines live code, markdown and data, through Microsoft's implementation, known as MS Azure Notebooks , putting together a small library of R and F# notebooks . As Microsoft's FAQ for the service describes it as : ...a multi-lingual REPL on steroids. This is a free service that provides Jupyter notebooks along with supporting packages for R, Python and F# as a service. This means you can just login and get going since no installation/setup is necessary. Typical usage includes schools/instruction, giving webinars, learning languages, sharing ideas, etc. Feel free to clone and comment... In R Azure Workbook for R - Memoisation and Vectorization Charting Correlation Matrices in R In F# Charnownes Constant in FSharp.ipynb Project Euler - Problems 18 and 67 - FSharp using Dynamic Programming
I 'cheated' solving this, using a hint for a limit on higher-end of the primes, since there is no built-in way to calculate square roots of Big Integer, other than constructing my own function using the Babylonian, aka Newton's, method.
Description
Solution
open System.Collections
open System.Numerics
let getPrimesInt64 max =
let primes = new BitArray(max+1, true)
seq { 2 .. max } |>
Seq.filter (fun n ->
if primes.[int n] then
for i in bigint n * bigint n..bigint n..bigint max do primes.[int i] <- false
primes.[int n])
//use this size for your array of primes
//let unitTest_P3_PrimeFactors_1_7 = getPrimesInt64 1000000
let FindLargestPrimeFactor (n:BigInteger) =
let primes = getPrimesInt64 1000000
let filteredList = primes |> Seq.filter(fun x -> n % bigint x = 0I)
Seq.max filteredList
let resultingPrimeFactor = FindLargestPrimeFactor 600851475143I
Description
- The prime factors of 13195 are 5, 7, 13 and 29.
- What is the largest prime factor of the number 600851475143?
Solution
open System.Collections
open System.Numerics
let getPrimesInt64 max =
let primes = new BitArray(max+1, true)
seq { 2 .. max } |>
Seq.filter (fun n ->
if primes.[int n] then
for i in bigint n * bigint n..bigint n..bigint max do primes.[int i] <- false
primes.[int n])
//use this size for your array of primes
//let unitTest_P3_PrimeFactors_1_7 = getPrimesInt64 1000000
let FindLargestPrimeFactor (n:BigInteger) =
let primes = getPrimesInt64 1000000
let filteredList = primes |> Seq.filter(fun x -> n % bigint x = 0I)
Seq.max filteredList
let resultingPrimeFactor = FindLargestPrimeFactor 600851475143I
Comments
Post a Comment