function isPrime(x) { if (x < 2) { return false } else if (x % 2 == 0) { return x == 2 } for (var i = 3; i * i <= x; ++i) { if (x % i == 0) { return false; } } return true; } function mag(x) { return x < 10 ? 10 : 10 * mag(x / 10) } function concat(x, y) { return x * mag(y) + y } function getPrimes(N) { p = new Array() for (var i = 2; i <= N; ++i) { if (isPrime(i)) { p.push(i) } } return p } function satisfies(p,s) { for (var i = 0; i < s.length; ++i) { if (!(isPrime(concat(s[i],p)) && isPrime(concat(p,s[i])))) { return false } } return true } function setSum(set) { sum = 0; for (var i = 0; i < set.length; ++i) { sum += set[i] } return sum } function scopy(set) { return set.slice(0) } primes = getPrimes(10000) function finishSet(set, target, start) { if (set.length == 5) { test = setSum(set) return test < target ? test : target } else { for (var i = start; i < primes.length; ++i) { p = primes[i] if (satisfies(p,set)) { cset = scopy(set) cset.push(p) test = finishSet(cset,target,i) if (test < target) { target = test break } } } } return target } /** this is 'main' */ function euler60() { ans = finishSet(new Array(),10000000,0) console.log(ans) alert(ans) }
Sunday, November 10, 2013
Problem 60 - Javascript
Problem 60 was a bit annoying - its a problem that I had never solved in my past life of doing Euler problems without language restrictions, but everything turned out O.K. My first solution was excessively slow (2-5min), but I noticed something really dumb I was doing that caused me to search way more combinations than necessary. The code below runs in <1s. And now I am formally up in another multiple of 10 - the 60's are upon us.
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment