So I am testing my algorithm and trying to print all prime numbers within a range. I think the code is logical but it keeps printing the wrong output i.e the unfiltered list of numbers.
function sumPrimes(num) {
// Check all numbers for primality
let a = []
let b = []
for (let i = 2; i <= num; i ) {
a.push(i)
b.push(i)
}
//console.log(a)
return a.filter(function(item) {
for(let j = 0; j < b.length; j ) {
if(item !== b[j] && item % b[j] != 0) {
return true
}
}
return false;
})
}
sumPrimes(977);
CodePudding user response:
There are few issues. First j
should start being equal to 2
. Otherwise it will see every value has a factor of 1. We can also skip your check to make sure b[j]
is not item
if we don't go through the entire span of b
and instead just up to item
. The other main issue is that the return true
and return false
are backwards.
The next issues are that you don't really need some parts. For example b[j]
will always be equal to j 2
so there is no need to build b
.
function sumPrimes(num) {
// Check all numbers for primality
let a = []
for (let i = 2; i <= num; i ) {
a.push(i)
}
return a.filter(function(item) {
for(let j = 2; j < item; j ) {
if(item % j === 0) {
// j is a factor so we shouldn't keep it and instead skip it
return false;
}
}
// We know that all of the values up to item are not factors so we keep it
return true;
})
}
console.log(sumPrimes(977));
Plus we can skip adding every value to a
if we apply the filtering as we add the values.
function getPrimesUpTo(num) {
let primes = [];
// Check each value
for (let i = 2; i <= num; i ) {
let hasFactors = false;
// Search for any factors before adding it to our list of primes
for (let possibleFactor = 2; possibleFactor < i; possibleFactor ) {
if (i % possibleFactor === 0) {
hasFactors = true;
break;
}
}
if (!hasFactors) {
primes.push(i);
}
}
return primes;
}
console.log(getPrimesUpTo(977));