Find prime numbers

find_primes.js

// Converted to Javascript by Daniel Bartlett [DanBUK] <dan@f-box.org>
// Source: http://en.wikibooks.org/wiki/Efficient_Prime_Number_Generating_Algorithms

var find_primes = function (max_prime) {
  /* Get the square root of the upper limit. This will be the upper limit of the test prime array
     for primes used to verify the primacy of any potential primes up to (max_prime). Primes greater than 
     (sqrtlim) will be placed in an array for extended primes, (xp), not needed for the verification
     test. The use of an extended primes array is technically unnecessary, but helps to clarify that we
     have minimized the size of the test prime array.
  */
  var sqrtlim = Math.sqrt(parseFloat(max_prime));
  // Initialize the variable for the potential prime, setting it to begin with the first prime number, (2).
  var pp = 2;
  /* Initialize the array for the skip set, setting it at a single member, being (pp=2). Although
     the value of the quantity of members in the skip set is never needed in the program, it may be
     useful to understand that future skip sets will contain more than one member, the quantity of which
     can be calculated, and is the quantity of members of the previous skip set multiplied by one less
     than the value of the prime which the new skip set will exclude multiples of. Example - the skip
     set which eliminates multiples of primes up through 3 will have (3-1)*1=2 members, since the
     previous skip set had 1 member. The skip set which eliminates multiples of primes up through 5 will
     have (5-1)*2=8 members, since the previous skip set had 2 members, etc.
  */
  var ss = [pp];
  // Initialize the array for primes which the skip set eliminate multiples of, setting the first
  // member as (pp=2) since the first skip set will eliminate multiples of 2 as potential primes.
  var ep = [pp];
  // Advance to the first potential prime, which is 3.
  pp++;
  /*
     Initialize an array for the ranges of each skip set, setting the first member to be the range
     of the first skip set, which is (ss[0]=2). Future skip sets will have ranges which can be 
     calculated, and are the sum of the members of the skip set. Another method of calculating the range
     will also be shown below.
  */
  var rss = [(ss[0])];
  /* Initialize an array for primes which are needed to verify potential primes against, setting the
     first member as (pp=3), since we do not yet have a skip set that excludes multiples of 3. Also note
     that 3 is a verified prime, without testing, since there are no primes less than the square root of 3.
  */
  var tp = [pp];
  // Initialize a variable for keeping track of which skip set range is current.
  var i = 0;
  /* Add a member to the array of skip set ranges, the value being the value of the previous skip
     set range, (rss[0]=2), multiplied by the value of the largest prime which the new skip set will
     exclude multiples of, (tp[0]=3), so 2*3=6. This value is needed to define when to begin
     constructing the next skip set.
  */
  rss.push(((rss[i]) * (tp[0])));
  /* Initialize an array for extended primes which are larger than the square root of the user
     defined limit (lim) and not needed to verify potential primes against, leaving it empty for now.
     Again, the use of an extended primes array is technically unnecessary, but helps to clarify that we
     have minimized the size of the test prime array.
  */
  var xp = [];
  /* Advance to the next potential prime, which is the previous potential prime, (pp=3), plus the
     value of the next member of the skip set, which has only one member at this time and whose value is
     (ss[0]=2), so 3+2=5.
  */
  pp += ss[0];
  // Initialize a variable for the next potential prime, setting its value as (pp=5).
  var npp = pp;
  /* Add a member to the array of test primes, the member being the most recently identified prime,
     (npp=5). Note that 5 is a verified prime without testing, since there are no TEST primes less than
     the square root of 5.
  */
  tp.push(npp);
  // Loop until the user defined upper limit is reached.
  while(npp < max_prime) {
    // Increment the skip set range identifier.
    i++;
    // Loop until the next skip set range is surpassed, since data through that range is
    // needed before constructing the next skip set.
    while(npp < ((rss[i]) + 1)) {
      // Loop through the current skip set array, assigning the variable (n) the value
      // of the next member of the skip set.
      for(var n in ss) {
        // Assign the next potential prime the value of the potential prime plus
        // the value of the current member of the skip set.
        npp = pp + ss[n];
        // If the next potential prime is greater than the user defined limit,
        // then end the 'for n' loop.
        if (npp > max_prime) break;
        // If the next potential prime is still within the range of the next skip
        // set, then assign the potential prime variable the value of the next
        if (npp <= ((rss[i]) + 1)) {
          pp = npp;
        }
        // Get the square root of the next potential prime, which will be the
        // limit for the verification process.
        var sqrtnpp = Math.sqrt(npp);
        // Set the verification flag to True.
        var test = true;
        // Loop through the array of the primes necessary for verification of the next potential prime.
        for(var q in tp) {
          // If the test prime is greater than the square root of the next
          // potential prime, then end testing through the 'for q' loop.
          if (sqrtnpp < tp[q]) break;
          // If the test prime IS a factor of the next potential prime.
          else if (npp % tp[q] == 0) {
            // Then set the verification flag to False since the next potential prime is not a prime number.
            test = false;
            // And end testing through the 'for q' loop.
            break;
          }
        } // for(var q in tp)
        // If the next potential prime has been verified as a prime number.
        if (test == true) {
          // And if the next potential prime is less than or equal to the
          // square root of the user defined limit, then add it to the array of
          // primes which potential primes must be tested against.
          if (npp <= sqrtlim) tp.push(npp);
          // Otherwise, add it to the array of primes not needed to verify potential primes against.
          else xp.push(npp);
        } // (test == true)
      } // for(var n in ss)
      // If the next potential prime is greater than the user defined limit, then end the 'while npp<rss[i]+1' loop.
      if (npp > max_prime) break;
    } // (npp < ((rss[i]) + 1))
    // If the next potential prime is greater than the user defined limit, then end the 'while npp<int(lim)' loop.
    if (npp > max_prime) break;
    // Initialize a variable for the last relevant potential prime and set its value to the value of the potential prime.
    var lrpp = pp;
    // Initialize an array for the next skip set, leaving it empty for now.
    var nss = [];
    // Loop until the construction of the new skip set has gone through the range of the new skip set.
    while(pp < ((((rss[i]) + 1) * 2) - 1)) {
      // Loop through the current skip set array.
      for(var n in ss) {
        // Assign the next potential prime the value of the potential prime plus the value of the current member of the skip set.
        npp = pp + ss[n];
        // If the next potential prime is greater than the user defined limit, then end the 'for n' loop.
        if (npp > max_prime) break;
        // Get the square root of the next potential prime, which will be the limit for the verification process.
        var sqrtnpp = Math.sqrt(npp);
        // Set the verification flag to True.
        var test = true;
        // Loop through the array of the primes necessary for verification of the next potential prime.
        for(var q in tp) {
          // If the test prime is greater than the square root of the next
          // potential prime, then end testing through the 'for q' loop.
          if (sqrtnpp < tp[q]) break;
          // If the test prime IS a factor of the next potential prime.
          else if (npp % tp[q] == 0) {
            // Then set the verification flag to False since the next potential prime is not a prime number.
            test = false;
            // And end testing through the 'for q' loop.
            break;
          }
        } // (var q in tp)
        // If the next potential prime has been verified as a prime number.
        if (test == true) {
          // And if the next potential prime is less than or equal to the
          // square root of the user defined limit, then add it to the array of
          // primes which potential primes must be tested against.
          if (npp <= sqrtlim) tp.push(npp);
          // Otherwise, add it to the array of primes not needed to verify potential primes against.
          else xp.push(npp);
        } // (test == true)
        /* If the next potential prime was NOT factorable by the first member of
           the test array, then it is relevant to the construction of the new skip set
           and a member must be included in the new skip set for a potential prime to
           be selected. Note that this is the case regardless of whether the next
           potential prime was verified as a prime, or not.
        */
        if (npp % tp[0] != 0) {
          // Add a member to the next skip set, the value of which is thedifference between
          // the last relevant potential prime and the next potential prime.
          nss.push((npp - lrpp));
          // Assign the variable for the last relevant potential prime the value of the next potential prime.
          lrpp = npp;
        } // (npp % tp[0] != 0)
        // Assign the variable for the potential prime the value of the next potential prime.
        pp = npp;
        
      } // (var n in ss)
      // If the next potential prime is greater than the user defined limit, then end the 'while pp < ((((rss[i]) + 1) * 2) - 1)' loop.
      if (npp > max_prime) break;
    } // (pp < ((((rss[i]) + 1) * 2) - 1))
    // If the next potential prime is greater than the user defined limit, then end the 'while npp<int(lim)' loop.
    if (npp > max_prime) break;
    // Assign the skip set array the value of the new skip set array.
    ss = nss;
    // Add a new member to the excluded primes array, since the newly constructed skip set will exclude all multiples of primes
    //  through the first member of the test prime array.
    ep.push(tp[0]);
    // Delete the first member from the test prime array since future potential primes will not have to be tested against this prime.
    tp.splice(0, 1);
    // Add a member to the skip set range array with the value of the range of the next skip set.
    rss.push(((rss[i]) * (tp[0])));
    // Assign the next potential prime the value of the last relevant potential prime.
    npp = lrpp;
  } // (npp < max_prime)
  // Flip the array of excluded primes.
  ep.reverse();
  // Add each member of the flipped array into the beginning of the test primes array.
  for(var n in ep) {
    tp.unshift(ep[n]);
  }
  // Flip the array of test primes.
  tp.reverse();
  // Add each member of the flipped array into the beginning of the extended primes array.
  for(var n in tp) {
    xp.unshift(tp[n]);
  }
  // Send the completed array of all primes up to the user defined limit back to the function call.
  return xp;
};