Created
March 26, 2013 02:34
-
-
Save kevincennis/5242673 to your computer and use it in GitHub Desktop.
Find the sum of all primes under 2,000,000 that contain a 7 or 9
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
var i, l, max = 2e6, primes = [], val = 0 | |
function isPrime( n ) { | |
var i = 2 | |
if ( n < 2 ) return false | |
if ( n == 2 ) return true | |
for ( ; i < n; ++i ) | |
if ( n % i === 0 ) | |
return false | |
return true | |
} | |
for ( i = 1; i < max; ++i ) | |
if ( isPrime(i) ) | |
primes.push(i) | |
for ( i = 0, l = primes.length; i < l; ++i ) | |
if ( /[7,9]/.test( '' + primes[i] ) ) | |
val += primes[i] | |
console.log(val) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
function sumPrimesWith7or9( n ) { | |
var s = Math.sqrt(n), h = {}, val = 0, i = 3, j | |
for ( ; i <= n; i += 2 ) { | |
if ( h[( i - 3 ) / 2] ) continue | |
if ( /[7,9]/.test( '' + i ) ) val += i | |
if ( i > s ) continue | |
for ( j = i * i; j <= n; j += i * 2 ) | |
h[( j - 3 ) / 2] = 1 | |
} | |
return val | |
} | |
console.log(sumPrimesWith7or9(2e6)) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Kevins-MacBook-Pro-2:Euler kevin$ time node obvious.js
121784919393
real 9m32.194s
user 9m33.049s
sys 0m1.887s
Kevins-MacBook-Pro-2:Euler kevin$ time node optimized.js
121784919393
real 0m0.185s
user 0m0.163s
sys 0m0.022s