What is the reason for my algorithm's inability to work with this specific number?

Question

What is the reason for my algorithm's inability to work with this specific number?

I'm currently working on creating an algorithm to compute the sum of prime numbers that are less than or equal to a specified number. Below is my attempt:

function calculatePrimeSum(num) {
// initialize an array with numbers up to the given num
  let prime = [], i = 2;
  while (prime.indexOf(num) < 0){
    prime.push(i)
    i++;
  }
// filter the array to only keep prime numbers and then sum them up
  let result = prime
  .filter(function (a){
    if(a === 2 ||a === 3 || a === 5 || a === 7){
      return a
    } else {
      return a % 2 > 0 && a % 3 > 0 && a % 5 > 0 && a % 7 > 0
  }}).reduce((a,b) => a+b)
  
  console.log(result)
  return result
}
calculatePrimeSum(977); //displays 108789 instead of 73156

In my filtering function, I check whether a number can be divided evenly by 2, 3, 5, or 7. If it leaves a remainder greater than zero, it's identified as a prime number. However, there seems to be an issue when the input is 977, resulting in an incorrect sum. Is there anyone who can identify what's causing this problem?

javascript typescript algorithm

Answer 1

Answer №1

After reviewing your code, it seems that your prime number checking logic is flawed. Merely because a number cannot be divided by 2, 3, 5, or 7 does not guarantee its primality. You can actually improve this by incorporating the prime checking method from the following link: Number prime test in JavaScript. By optimizing your loop, you will only need to iterate once.

The corrected approach involves initializing a for loop starting from the smallest prime number, which is 2, and incrementing it until it meets your desired number. Within this loop, each number is checked for primality, and if it is prime, it is added to the sum.

This revised method offers several advantages:

Avoids storing a large array of prime numbers in the prime array, as they are directly summed up without requiring storage. This assumes that the prime numbers are not needed for other purposes.
Eliminates the need for multiple iterations compared to your previous code. The previous version involved repeated iterations within the while loop to generate all numbers, the filter for prime check, and the final summation using the reduce method.

// Adapted from: https://stackoverflow.com/questions/40200089/number-prime-test-in-javascript
function isPrime(num) {
  for (let i = 2, s = Math.sqrt(num); i <= s; i++)
    if (num % i === 0) return false;
  return num > 1;
}

function sumPrimes(num) {
  let sum = 0;
  
  for (let n = 2; n <= num; n++) {
    if (isPrime(n)) {
      sum += n;
    }
  }

  console.log(sum);
  return sum;
}
sumPrimes(977); // Outputs 73156 as expected

Answer 2

After reviewing your code, it seems that your prime number checking logic is flawed. Merely because a number cannot be divided by 2, 3, 5, or 7 does not guarantee its primality. You can actually improve this by incorporating the prime checking method from the following link: Number prime test in JavaScript. By optimizing your loop, you will only need to iterate once.

The corrected approach involves initializing a for loop starting from the smallest prime number, which is 2, and incrementing it until it meets your desired number. Within this loop, each number is checked for primality, and if it is prime, it is added to the sum.

This revised method offers several advantages:

Avoids storing a large array of prime numbers in the prime array, as they are directly summed up without requiring storage. This assumes that the prime numbers are not needed for other purposes.
Eliminates the need for multiple iterations compared to your previous code. The previous version involved repeated iterations within the while loop to generate all numbers, the filter for prime check, and the final summation using the reduce method.

// Adapted from: https://stackoverflow.com/questions/40200089/number-prime-test-in-javascript
function isPrime(num) {
  for (let i = 2, s = Math.sqrt(num); i <= s; i++)
    if (num % i === 0) return false;
  return num > 1;
}

function sumPrimes(num) {
  let sum = 0;
  
  for (let n = 2; n <= num; n++) {
    if (isPrime(n)) {
      sum += n;
    }
  }

  console.log(sum);
  return sum;
}
sumPrimes(977); // Outputs 73156 as expected

Answer 3

Answer №2

In order to determine if a number is prime, it must not be divisible by any other prime numbers. While your approach is on the right track, you need to continuously add more primes to your array for accurate results. This can be done using the following function:

const findPrimes = (n) => {
    var primes = [2];
    if (n<2) return [];
    if (n===2) return [2];
    for (let i=3;i<=n;i+=2) if (primes.every(x=>i%x)) primes.push(i);
    return primes;
  }

We begin with the first prime number and then proceed to check every second number starting from 3, since all even numbers are divisible by 2. As we iterate through i+2, we simply verify if i is divisible by any of the previously identified prime numbers. If it is not divisible (i%x), we expand our array of primes by adding i to it.

Answer 4

In order to determine if a number is prime, it must not be divisible by any other prime numbers. While your approach is on the right track, you need to continuously add more primes to your array for accurate results. This can be done using the following function:

const findPrimes = (n) => {
    var primes = [2];
    if (n<2) return [];
    if (n===2) return [2];
    for (let i=3;i<=n;i+=2) if (primes.every(x=>i%x)) primes.push(i);
    return primes;
  }

We begin with the first prime number and then proceed to check every second number starting from 3, since all even numbers are divisible by 2. As we iterate through i+2, we simply verify if i is divisible by any of the previously identified prime numbers. If it is not divisible (i%x), we expand our array of primes by adding i to it.

Answer 5

Answer №3

Presented below is an enhanced and optimized version of the Erastostenes sieve algorithm that guarantees scalability while maintaining high performance. This particular implementation includes a limit for testing numbers up to the square root of the current number:

function findPrimes(limit){
  for (var primes=[],i=1,j=0,cap=2; ++i<=limit;){
    if (i>2 && i==cap) cap=primes[j]*primes[j++];
    if (primes.slice(0,j-1).every(p=>i%p)) primes.push(i)
  }
  return primes;
}

let primeArray=findPrimes(977);
console.log("sum of primes:", primeArray.reduce((a,c)=>a+=c));
console.log("list of primes:", primeArray.join(" "));

Answer 6

Presented below is an enhanced and optimized version of the Erastostenes sieve algorithm that guarantees scalability while maintaining high performance. This particular implementation includes a limit for testing numbers up to the square root of the current number:

function findPrimes(limit){
  for (var primes=[],i=1,j=0,cap=2; ++i<=limit;){
    if (i>2 && i==cap) cap=primes[j]*primes[j++];
    if (primes.slice(0,j-1).every(p=>i%p)) primes.push(i)
  }
  return primes;
}

let primeArray=findPrimes(977);
console.log("sum of primes:", primeArray.reduce((a,c)=>a+=c));
console.log("list of primes:", primeArray.join(" "));

Answer 7

Answer №4

Optimal and efficient solution using the prime-lib library:

import {generatePrimes, stopOnValue} from 'prime-lib';

const result = stopOnValue(generatePrimes(), 977);

let total = 0;
for (let num of result) {
    total += num;
}

console.log(total); //=> 73156

Answer 8

Optimal and efficient solution using the prime-lib library:

import {generatePrimes, stopOnValue} from 'prime-lib';

const result = stopOnValue(generatePrimes(), 977);

let total = 0;
for (let num of result) {
    total += num;
}

console.log(total); //=> 73156

What is the reason for my algorithm's inability to work with this specific number?

Answer №1

Answer №2

Answer №3

Answer №4

Similar questions

Angular view fails to update after form submission when using ngDialog to change the scope

Unexpected errors are encountered when using ng serve

Conceal the element at all times

Step-by-step guide on duplicating a div a set number of times

Utilize mapping for discriminated union type narrowing instead of switch statements

The functionality of the AngularJS nested router is not functioning properly

What is the meaning of "bootstrapping" as it relates to Angular 2?

clearInterval function is not functioning

Flask and the steps to modify CORS header

Is locking Node and npm versions necessary for frontend framework projects?

I am looking to manage the error handling service, and my next step is to intentionally insert a single error into my service and have it automated

What is the best way to convert API data into a currency format?

The function of TypeScript map is not working properly

SailsJS failing to detect changes in local JSON file

Guide to defining a typescript class property using an index signature

What might be causing the issue of a click handler not registering during the initial page load when using Enquire.js

To handle a 400 error in the server side of a NextJS application, we can detect when it

How can I retrieve the name of a constant enum member in TypeScript as a string?

Only when the condition is satisfied in AngularJS will I include JSON data

Having trouble with Lerna bootstrap? You might be running into the dreaded npm error code E401