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

Creating a Typescript interface that includes keys from another interface

Retrieve the data from every dropdown menu

Sending fragmented files straight to Amazon's s3

After the component has been initialized for the second time, the elementId is found to be null

Encountering an error message stating, "Unable to assign value to 'onclick' property"

Utilizing the Bing Translation API to translate an entire webpage

Expanding a JavaScript list using HTML inputs

Advanced automatic type inference for object literals in TypeScript

The output from VScode-Code-Runner is limited to just the directory, with no additional

Executing specific rendering procedures based on conditions for mapped data - React

Utilizing jQuery to correspond with CSS media queries

Using Javascript within an HTML document may not provide the intended functionality

One way to showcase a single piece of data without the need for looping is by utilizing the `

Guide to implementing the patchValues() method in conjunction with the <mat-form-field> within the (keyup.enter) event binding

Retrieve a particular item using the NGXS selector and incorporate it into the template

Converting a string URL to an object type in TypeScript

What are alternative ways to communicate with the backend in Backbone without relying on model.save()?

Is there a method to accurately pinpoint the specific type?

How to pass parameters while updating parent values in VueJS using emit?

Can you explain the process of obtaining getServerSideProps results for my IndexPage?