DEV Community

Discussion on: Solving "Sum All Primes" / freeCodeCamp Algorithm Challenges

Collapse
 
ttatsf profile image
tatsuo fukuchi • Edited

You can do it faster to use Math.sqrt(n) instead of n/2. :

function isPrime(n) {
  if (n <= 1) return false;
  for (let i = 2; i <= Math.sqrt(n); i++) {
    if (n % i === 0) {
      return false;
    }
  }
  return true;
}

If you need more speed / efficiency, you can use the memoizer function to get primes:

const memoizer = inits => rule =>{
  const memo = [...inits]
  const a = n => {
    if(n >= memo.length) {
      for(let i = memo.length; i <= n; i++) {
        memo[i] = rule( a )( i )
      }
    }
    return memo[n]  
  }
  return a
}

const nomineeG = value => function*(){
  let m = Math.ceil(value / 6) * 6
  if ( value === m - 5 ) yield m - 1
  while (true) {
    yield  m + 1
    yield  m + 5
    m = m + 6
  }
}()

const isAllIndivisible = a => value => {
  const end = Math.sqrt(value) 
  for (let i = 0; a(i) <= end; i++){
    if (value % a(i) === 0) return false
  }
  return true
}

const primeInits = [2, 3, 5]

const primeRule = a => n => {
  for (const nominee of nomineeG( a(n - 1) ) ) {
    if ( isAllIndivisible(a)(nominee) ) return nominee
  }
}

const primeAt = memoizer( primeInits )( primeRule )

const primeG = function*(){
  let i = 0
  while (true) {
    yield primeAt(i)
    i = i + 1
  }
}

const sumPrimes = n =>{
  let sum = 0
  for ( const v of primeG() ) {
    if ( v > n ) return sum
    sum = sum + v
  }
}