Community

Start a Thread
Filters
By Category
Notifications
Subscribe You’re not receiving notifications from this thread.

Sum All Primes (Main Thread)

Here is the interview question prompt, presented for reference.

You're given a number n. Can you write a method sumOfAllPrimes that finds all prime numbers smaller than or equal to n, and returns a sum of them?

For example, we're given the number 15. All prime numbers smaller than 15 are:

2, 3, 5, 7, 11, 13

They sum up to 41, so sumOfAllPrimes(15) would return 41.

Constraints

  • n will always be a non zero positive integer <= 100000
  • Expected time complexity : O(nlogn)
  • Expected space complexity : O(n)

You can see the full challenge with visuals at this link.

Challenges • Asked over 4 years ago by Anonymous

Jake from AlgoDaily Commented on Jul 21, 2020:

This is the main discussion thread generated for Sum All Primes.

Anonymous Commented on Jul 21, 2020:

sumOfAllPrimes(15) should return 65, as the question asks for all prime numbers smaller than or equal to n correct?

Anonymous Commented on Jul 21, 2020:

Never mind I misread the question

Giovani Commented on May 04, 2021:

This solution is O(n log n), right? But O(1) in space

SNIPPET
function sumOfPrimes(n) {
  let total = 0;

  for(let i = 2; i <= n; i++) {
    if(isPrime(i)) {
      total += i;
    }
  }

  return total;
}

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

  return true;
}