Project Euler in Nim
February 15, 2015
After a discussion on firstname.lastname@example.org, I decided to spend the majority of my day playing with Nim. I used it to solve the first three Project Euler problems, with a unnecessarily complicated dynamic programming solution to problem #2.
I know posting solutions to PE problems is looked down upon, but the first three problems are trivial, and solutions can undoubtedly be found elsewhere online.
If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.
Find the sum of all the multiples of 3 or 5 below 1000.
var sum = 0 for i in 1..999: if i mod 3 == 0 or i mod 5 == 0: sum += i echo sum
Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …
By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.
# Of course, this solution is unnecessarily complicated, but that's as an excuse # to try out more language features! import tables type MemoFunc = proc (a: int): int proc memoize(f: MemoFunc): MemoFunc = var previous = initTable[int, int]() return proc(i: int): int = if not previous.hasKey i: previous[i] = f(i) return previous[i] # fib must be declared *before* use in the anonymous proc, otherwise nim won't # be able to find it, as nim has static binding var fib: proc(a: int): int fib = memoize do (i: int) -> int: if i == 0 or i == 1: return 1 return fib(i-1) + fib(i-2) var sum = 0 i = 0 while true: if fib(i) > 4_000_000: break if fib(i) mod 2 == 0: sum += fib(i) i += 1 echo sum
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?
var remaining = 600_851_475_143 # `..` retains a reference to `remaining`, not a value, unlike python's `range` for i in 2..remaining: if remaining mod i == 0: remaining = remaining div i echo "found prime factor: ", i
The views expressed on this site are my own and do not reflect those of my employer.