Instantly share code, notes, and snippets.

# Noitidart/_js-primesBetween.js Last active Feb 19, 2017

_js-primesBetween.js
 function primesBetween(min, max) { // inclusive // collect all possible dividends let dividends = []; for (let i=min; i<=max; i++) // inclusive dividends.push(i); // console.log('dividends:', dividends); ////// method 1 // collect all possible divisors let divisormax = Math.floor(Math.pow(max, 0.5)); // divisormax is definitely prime, per sieve of erastothenes - https://codility.com/media/train/9-Sieve.pdf let divisors = []; const isPrime = int => { for (let divisor of divisors) if (int % divisor === 0) return false; return true; }; for (let divisor=2; divisor<=divisormax; divisor++) // start at 2, because 0 and 1 are not valid divisors of a prime if (isPrime(divisor)) divisors.push(divisor); // console.log('divisors:', divisors); // remove all multiples of `divisors` in `dividends` let primesall = []; let primes = dividends.filter(dividend => { let divisormax = Math.floor(Math.pow(dividend, 0.5)); // max divisor for `dividend` // console.log('START - testing primeness of dividend:', dividend); for (let divisor of divisors) { if (divisor > divisormax) { // console.log(`BREAK. divisor (\${divisor}) is greater than divisormax (\${divisormax}) for this dividend (\${dividend}).`); break; } // // let minmultiple = divisor * divisor; // min multiple divisor should start working on // // if (dividend < minmultiple) { // // console.log(`CONTINUE. dividend (\${dividend}) is less than minmultiple (\${minmultiple}) for this divisor (\${divisor}).`); // // continue; // // } // console.log(dividend, '%', divisor, '=', dividend % divisor, 'minmultiple:', minmultiple); if (dividend % divisor === 0) { return false; // its divisible, discard it } } return true; // keep it, its prime }); // ////// method 2 - trying to get super performant // // remove all multiples of `divisors` in `dividends` method 1 // let primes = dividends.slice(); // let divisors = []; // collected divisors, will all be prime per sieve of erastothenes // const isPrime = int => { // for (let divisor of divisors) { // if (int % divisor === 0) { // return false; // } // } // return true; // }; // let divisor = 2; // while (divisor * divisor <= max) { // // test if `divisor` is prime - if not divisible by any of the divisors so far, then its prime // if (!isPrime(divisor)) { // console.log(divisor, 'is not prime, so impossible for it to be a divisor'); // being a divisor means lowest factor. being a lowest factor means its prime. per sieve of erastothenes // divisor++; // continue; // } // divisors.push(divisor); // let minmultiple = divisor * divisor; // first multiple of divisor i need to start removing // while (k <= max) { // primes[k] = 0; // k += divisor; // } // i++ // } // // let primes = divisors; ///// end methods // console.log('primes:', primes); return primes; }
Owner

• Doesnt work

### Rev2

• Works, just uncommented method 1

### Rev3

• I think its a perf enhancement, as I don't add to divisors unless it is prime now

### Rev4

• Tried to work in the minimum multiple of a divisor rule into method 1. I think calculating the max divisor for it, does the trick. Because in my tests, the `continue` block is never getting called here is rev4 code with the console logging and `continue` block:

``````function primesBetween(min, max) {
// inclusive

// collect all possible dividends
let dividends = [];
for (let i=min; i<=max; i++) // inclusive
dividends.push(i);

console.log('dividends:', dividends);

////// method 1
// collect all possible divisors
let divisormax = Math.floor(Math.pow(max, 0.5)); // divisormax is definitely prime, per sieve of erastothenes - https://codility.com/media/train/9-Sieve.pdf
let divisors = [];
const isPrime = int => {
for (let divisor of divisors)
if (int % divisor === 0) return false;
return true;
};
for (let divisor=2; divisor<=divisormax; divisor++) // start at 2, because 0 and 1 are not valid divisors of a prime
if (isPrime(divisor)) divisors.push(divisor);

console.log('divisors:', divisors);

// remove all multiples of `divisors` in `dividends`
let primesall = [];
let primes = dividends.filter(dividend => {
let divisormax = Math.floor(Math.pow(dividend, 0.5)); // max divisor for `dividend`
console.log('START - testing primeness of dividend:', dividend);
for (let divisor of divisors) {
if (divisor > divisormax) {
console.log(`BREAK. divisor (\${divisor}) is greater than divisormax (\${divisormax}) for this dividend (\${dividend}).`);
break;
}
let minmultiple = divisor * divisor; // min multiple divisor should start working on
if (dividend < minmultiple) {
console.log(`CONTINUE. dividend (\${dividend}) is less than minmultiple (\${minmultiple}) for this divisor (\${divisor}).`);
continue;
}
console.log(dividend, '%', divisor, '=', dividend % divisor, 'minmultiple:', minmultiple);
if (dividend % divisor === 0) {
return false; // its divisible, discard it
}
}
return true; // keep it, its prime
});

// ////// method 2 - trying to get super performant
// // remove all multiples of `divisors` in `dividends` method 1
// let primes = dividends.slice();
// let divisors = []; // collected divisors, will all be prime per sieve of erastothenes
// const isPrime = int => {
//     for (let divisor of divisors) {
//         if (int % divisor === 0) {
//             return false;
//         }
//     }
//     return true;
// };
// let divisor = 2;
// while (divisor * divisor <= max) {
//     // test if `divisor` is prime - if not divisible by any of the divisors so far, then its prime
//     if (!isPrime(divisor)) {
//         console.log(divisor, 'is not prime, so impossible for it to be a divisor'); //  being a divisor means lowest factor. being a lowest factor means its prime. per sieve of erastothenes
//         divisor++;
//         continue;
//     }
//     divisors.push(divisor);
//     let minmultiple = divisor * divisor; // first multiple of divisor i need to start removing
//     while (k <= max) {
//         primes[k] = 0;
//         k += divisor;
//     }
//     i++
// }
//
// let primes = divisors;

///// end methods
console.log('primes:', primes);
return primes;

}
``````