Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
_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;
}
@Noitidart
Owner
Noitidart commented Feb 19, 2017 edited

README

Rev1

  • 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;
    
    }
    
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment