Сумма простых чисел для большого диапазона ввода

Question

Я пишу код, чтобы найти сумму всех простых чисел ниже заданного числа (в данном случае я хочу найти его за 2000000)

Мой код будет хорошо работать для чисел, например, 20000 и ниже, но, как я добавлю к нему 0, он не будет.

Я попытался запустить его на codesandbox, и он скажет мне, что где-то есть потенциальный бесконечный цикл.

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

Answer 1

Если вам нужно обрабатывать числа, превышающие 2 000 000, то это не правильный способ решения проблемы. Существует много алгоритмов для определения того, является ли число простым, и существует компромисс между сложностью алгоритма и эффективностью для больших чисел. Чтобы узнать, какой алгоритм подходит для вашего варианта использования, нам нужно знать, каков ваш вариант использования. (Похоже, вы пытаетесь решить данную проблему с помощью курса или кода).

Но даже с помощью используемого вами алгоритма есть простые способы ускорить его. С одной стороны, в цикле в isPrime, когда number % i === 0, вы должны return false вместо того, чтобы увеличивать переменную и проверять ее позже. Это изменение само по себе должно значительно ускорить вашу программу, потому что большинство чисел имеют небольшие делители, и поэтому большинство чисел будет выполнять этот цикл только несколько раз.

Еще одно простое ускорение - ограничить количество циклов. Вы перебираете все числа от 2 до n. Но чтобы проверить, является ли число простым, вам нужно только проверить его делимость на простые числа. Если ваша цель состоит в том, чтобы вычислить сумму первых, скольких простых чисел, то это легко: составьте список простых чисел, сравнивая каждого нового кандидата с числами, уже имеющимися в вашем списке. Я сильно подозреваю, что этот подход будет более чем достаточно быстрым для ваших нужд.

Answer 2

Более эффективным является использование сита Эратосфена. Обычно это возвращает список простых чисел до заданного предела, но с небольшой адаптацией с reduce вы можете сделать так, чтобы она возвращала сумму:

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

Обратите внимание, что существуют методы, позволяющие добиться еще большей производительности, например, сегментированное сито Эратосфена .

Answer 3

Просто подумал, что я подкреплю ответ Тома Смита с примером реализации:

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() разработан специально для вызова с увеличивающимся вводом n. Если проверено большее простое число n до меньшее простое число n, то условие

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

не удастся добавить меньшее простое число в список известных простых чисел, но, поскольку такая ситуация не возникает при таком использовании, этого достаточно.