Sum of prime numbers for large range input

Question

I am writing code to find the sum of all primes below a given number (in this case I want to find it for 2000000)

My code will run just fine for numbers like 20000 and lower, but as I add 0s to it, it won't.

I tried to run it on codesandbox and it'll tell me there's a potential infinite loop somewhere.

const isPrime = number => {

  let k=0

  for (let i=2; i < number; i++) {
    if (number % i === 0) {
    k++
    }
  }
  if (k === 0) {
    return true
  } else {
      return false
  } 
}

const sumOfPrimes = limit => {

  let primeSum = 0
  for (let i=1; i <= limit; i++) {
    if (isPrime(i)) {
        primeSum += i
    }
  } console.log(primeSum);
}

sumOfPrimes(2000000);

"*potential infinite loop*" doesn't mean that you have an infinite loop, it just means that it's running really long. That's expected, your algorithm has a square time complexity. And no, it doesn't chew up memory - in fact you should use some more memory and trade it for better running time. — Bergi, Jun 23 '19 at 17:04
There are some things you can do to speed this up. First you should exit early from the for loop. Once you've found out it's not prime, just return `if (number % i === 0) return false`. Also you only need to check up to the square root of a number. Still it's going to be slow for 2000000. — Mark, Jun 23 '19 at 17:10
Your `isPrime` is very suboptimal. Two simple improvements would be to only iterate to `Math.sqrt(number)`, and to `return false` from within the `for` loop on the first encountered factor rather than counting all the factors. If it has just one factor, you already know it's not a prime number. — Patrick Roberts, Jun 23 '19 at 17:11
https://www.freecodecamp.org/news/understanding-memoize-in-javascript-51d07d19430e/ — Manos Kounelakis, Jun 23 '19 at 18:22

Thom Smith · Answer 1 · 2019-06-23T17:16:37.740

If you have to handle numbers as large as 2,000,000, then this is not the right way to solve the problem. There are many algorithms for determining whether a number is prime, and there is a tradeoff between the complexity of the algorithm and the efficiency for large numbers. In order to know what algorithm is right for your use case, we would need to know what your use case is. (It sounds like you're trying to solve a given problem from a course or code challenge.)

But even with the algorithm you're using, there are easy ways to speed it up. For one thing, in the loop in isPrime, when number % i === 0, you should return false rather than incrementing a variable and checking it later. This change, by itself, should dramatically speed up your program, because most numbers have small divisors, and so most numbers will only run that loop a few times.

Another easy speedup is to limit the numbers you loop over. You're iterating over all numbers from 2 to n. But to check whether a number is prime, you only need to check its divisibility by prime numbers. If your goal is to compute the sum of the first however many prime numbers, then this is easy: build a list of prime numbers, checking each new candidate against the numbers already in your list. I strongly suspect that this approach will be more than fast enough for your needs.

trincot · Answer 2 · 2019-06-23T17:38:26.473

2

More efficient is to use the sieve of Eratosthenes. Normally that would return a list of primes up to a given limit, but with a small adaptation with reduce you can make it return the sum:

function sumOfPrimes(n) {
    const nums = Array(n).fill(true); 
    nums[0] = nums[1] = false;
    const sq = Math.sqrt(n);

    for (let i = 2; i <= sq; i++) {
        if (nums[i]) {
            for (let j = i * i; j < n; j += i) nums[j] = false;
        }
    }
    
    return nums.reduce((sum, a, i) => sum + (a && i), 0);
}


console.log(sumOfPrimes(10));
console.log(sumOfPrimes(2000000));

Note that there are methods to get even better performance, like the segmented sieve of Eratosthenes.

edited Jun 23 '19 at 17:38

answered Jun 23 '19 at 17:20

trincot

317,000
35
244
286

Funnily enough, I recently provided [an answer on how to optimize the memory usage of a sieve in JavaScript](https://stackoverflow.com/a/56617411/1541563). I know it's out of the scope of this particular question, but maybe the link will help anyone who comes across this answer and gets out of memory exceptions with larger input. (although since you're using `Boolean`, I'm not actually sure how the memory usage compares) – Patrick Roberts Jun 23 '19 at 17:56

Patrick Roberts · Answer 3 · 2019-06-23T17:47:50.337

Just thought I'd back up Thom Smith's answer with an example implementation:

const primes = [2, 3];

function isPrime (n) {
  // eliminate base cases
  if (n < 2) return false;

  const sqrt = Math.sqrt(n);
  let i;

  // check if known primes are factors of n
  for (i of primes) {
    if (i > sqrt) break;
    if (n % i === 0) return false;
  }

  // check if odd numbers between largest
  // known prime and sqrt(n) are factors of n
  for (i += 2; i <= sqrt; i += 2) {
    if (n % i === 0) return false;
  }

  // prevents duplicate primes from being added
  if (primes[primes.length - 1] < n) {
    primes.push(n);
  }

  return true;
}

function sumOfPrimes (limit) {
  let primeSum = 0;

  for (let i = 1; i <= limit; i++) {
    if (isPrime(i)) primeSum += i;
  }

  return primeSum;
}

console.log(sumOfPrimes(10));
console.log(sumOfPrimes(2000000));

isPrime() is designed specifically for being called with increasing input n. If a larger prime n is checked before a smaller prime n, then the condition

if (primes[primes.length - 1] < n)

will fail to add the smaller prime to the list of known primes, but since that situation does not occur with this usage, it is sufficient.

Sum of prime numbers for large range input

3 Answers3