CODEWITHSUNDEEP
javascriptloops
thedogknows
thedogknows

Reputation: 21

Sum of prime numbers for large range input

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);

Upvotes: 2

Views: 446

Answers (3)

Patrick Roberts
Patrick Roberts

Reputation: 51946

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.

Upvotes: 0

trincot
trincot

Reputation: 350951

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.

Upvotes: 2

Thom Smith
Thom Smith

Reputation: 14086

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.

Upvotes: 2

Related Questions