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