_js-primesBetween.js

_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;

}

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;
  
  }