VCHS Computer Science: Prime Factorization

Computes the prime factorization of each integer from 2 to N. Displays the last M results.

N: M:

Primality Algorithm:

Source Code

<style>
  label {
    font-style: italic;
  }
  th {
    font-weight: normal;
    font-style: italic;
  }
</style>

Computes the prime factorization of each integer from 2 to <i>N</i>.
Displays the last <i>M</i> results.
<p>
<label>N:</label>
<input id="upper-limit" type="number" min="2" value="5" step="1">
<label>M:</label>
<input id="tail-size" type="number" min="0" max="100" value="5" step="1">
</p><p>
<label>Primality Algorithm:</label>
<select id="algorithm-selector">
  <option value="0" label="All Algorithms"></option>
  <option value="1" label="Always Compute Primality (Slowest Algorithm)"></option>
  <option value="2" label="Always Compute Primality (Faster Algorithm)"></option>
  <option value="3" label="Compute Primality (Faster) and Cache"></option>
  <option value="4" label="50/50: Compute (Faster) and Cache / Use Prime Sieve"></option>
  <option value="5" label="Use Prime Sieve"></option>
</select>
</p><p>
<button id="execute-button">Execute</button>
</p><p id="the-output"></p>

<script>
function Cache() {
  this.get = get;
  this.set = set;
  const cache = {}
  function get(key) { return cache[key]; }
  function set(key, value) { return cache[key] = value; }
}

function Num(initialValue) {

this.valueOf = valueOf;
  this.toString = toString;
  this.isEvenlyDivisibleBy = isEvenlyDivisibleBy;
  this.isInteger = isInteger;
  this.isPositive = isPositive;
  this.isPositiveInteger = isPositiveInteger;
  this.isPrime = isPrime;
  this.isRightPrime = isRightPrime;
  this.isLeftPrime = isLeftPrime;
  this.getSmallestPrimeGreaterThan = getSmallestPrimeGreaterThan
  this.getPrimesLessThan = getPrimesLessThan;
  this.getPrimesLessThanOrEqualTo = getPrimesLessThanOrEqualTo;
  this.getPrimeFactorizationOf = getPrimeFactorizationOf;
  
  const value = initialValue;
  Object.freeze(this);
  
  function valueOf() { return value }
  function toString() { return value.toString(); }
  function isEvenlyDivisibleBy(otherNum) { return (value % otherNum.valueOf()) === 0; }
  function isInteger() { return value === Math.floor(value); }
  function isPositive() { return value > 0; }
  function isPositiveInteger() { return isPositive() && isInteger(); }
  function isPrime() { return Num.primeTester.getIsPrime(value); }
  function getSmallestPrimeGreaterThan() {
    let i = Math.floor(value);
    let p;
    do {
      i = i + 1;
      p = new Num(i);
    } while (!p.isPrime());
    return p;
  }
  function getPrimesLessThan() {
    const p = [];
    let n = new Num(2);
    while (n.valueOf() < value) {
      p.push(n.valueOf());
      n = n.getSmallestPrimeGreaterThan();
    }
    return p;
  }
  function getPrimesLessThanOrEqualTo() {
    return (new Num(value + 1)).getPrimesLessThan();
  }
  function getPrimeFactorizationOf() {
    if (!isInteger() || value < 2) return []; // [] is the emtpy set.
    if (isPrime()) return [value];
    // If a value is not prime and is an integer greater than or equal
    // to 2, then it has at least one prime factor; moreover, all of the
    // (prime) factors of such a value must be less than or equal to the
    // square root of the value.
    const upper = new Num(Math.sqrt(value));
    const candidates = upper.getPrimesLessThanOrEqualTo();
    const i = candidates.findIndex(isEvenlyDivisibleBy);
    const primeFactor = candidates[i];
    const smallerNum = new Num(value / primeFactor);
    const factorization = smallerNum.getPrimeFactorizationOf();
    // Add primeFactor to the beginning of the list:
    factorization.unshift(primeFactor);
    return factorization;
  }
  function isRightPrime() {
    let s = value.toString();
    const len = s.length;
    for (let upper = len; upper > 0; --upper)
      if (!new Num(parseInt(s.substring(0, upper))).isPrime())
        return false;
    return true;
  }
  function isLeftPrime() {
    let s = value.toString();
    const len = s.length;
    for (let lower = 0; lower < len; ++lower)
      if (!new Num(parseInt(s.substring(lower, len))).isPrime())
        return false;
    return true;
  }
}
Num.primeTester = undefined;

// MAIN PROGRAM

document.getElementById("execute-button").addEventListener("click", function() {

const outputElement = document.getElementById("the-output");
  const tailSizeElement = document.getElementById("tail-size");
  const upperLimitElement = document.getElementById("upper-limit");
  const algorithmSelectorElement = document.getElementById("algorithm-selector");
  const max = upperLimitElement.value;  
  let output = "";
  
  outputElement.innerHTML = "Determining the prime factorization of each integer from 2 to " + max + "...";

setTimeout( function() {
    console.log(algorithmSelectorElement);
    const id = parseInt(algorithmSelectorElement.value);

if (id === 0 || id === 1) {
      const algorithm = algorithmSelectorElement.options[1].label;
      Num.primeTester = PrimeTester;
      test(1, algorithm);
    }
    if (id === 0 || id === 2) {
      const algorithm = algorithmSelectorElement.options[2].label;
      Num.primeTester = BetterPrimeTester;
      test(2, algorithm);
    }
    if (id === 0 || id === 3) {
      const algorithm = algorithmSelectorElement.options[3].label;
      Num.primeTester = new PrimeCache();
      test(3, algorithm);
    }
    if (id === 0 || id === 4) {
      const algorithm = algorithmSelectorElement.options[4].label;
      Num.primeTester = new PrimeSieveCache(max/2);
      test(4, algorithm);
    }
    if (id === 0 || id === 5) {
      const algorithm = algorithmSelectorElement.options[5].label;
      Num.primeTester = new PrimeSieveCache(max);
      test(5, algorithm);
    }
    outputElement.innerHTML = output;

}, 500);

function test(id, name) {

const tailSize = tailSizeElement.value;
    output += "<h4>" + id + ". " + name + "</h4>";
    output += "\n<p><table>";
    output += "\n<tr>";
    output += "\n<th style='text-align:right'>#:</th><th>Prime Factorization</th>";
    output += "\n</tr>";

const begin = Date.now();
    for (let i = 2; i <= max; ++i) {
      const col1 = "<td style='text-align:right'>" + i + ":</td>";
      const col2 = "<td>" + new Num(i).getPrimeFactorizationOf() + "</td>";
      if (max - i < tailSize) {
        output += "\n<tr>\n" + col1 + col2 + "\n</tr>";
      }
    }
    const end = Date.now();
    output += "\n</table></p>";
    output += "<p>Elapsed time: " +  (end - begin) + "ms</p>";
  }
});
</script>

Pages

Prime Factorization

Source Code