GCD / LCM

Standalone, zero-dependency JavaScript implementation powering this tool. Free to inspect, copy, and build upon.

function primeFactors(n) {
    const f = {};
    let d = 2;
    while (d * d <= n) {
      while (n % d === 0) { f[d] = (f[d] || 0) + 1; n = Math.floor(n / d); }
      d++;
    }
    if (n > 1) f[n] = (f[n] || 0) + 1;
    return f;
  }

  function factStr(f) {
    return Object.entries(f).map(([p,e]) => e > 1 ? `${p}^${e}` : p).join(' × ') || '1';
  }

  function gcdTwo(a, b) { while (b) { [a,b] = [b, a%b]; } return a; }
  function lcmTwo(a, b) { return (a / gcdTwo(a,b)) * b; }

  function calculate() {
    const raw = document.getElementById('numInput').value;
    const errEl = document.getElementById('errMsg');
    errEl.style.display = 'none';
    document.getElementById('resultGrid').style.display = 'none';
    document.getElementById('stepsSection').style.display = 'none';
    document.getElementById('coprimeNote').style.display = 'none';

    const nums = raw.split(/[,\s]+/).map(s => parseInt(s.trim())).filter(n => !isNaN(n) && n > 0);
    if (nums.length < 2) { if (raw.trim()) { errEl.textContent = 'Enter at least 2 positive integers.'; errEl.style.display = ''; } return; }
    if (nums.some(n => n > 1e12)) { errEl.textContent = 'Numbers must be ≤ 1,000,000,000,000.'; errEl.style.display = ''; return; }

    const gcd = nums.reduce(gcdTwo);
    const lcm = nums.reduce(lcmTwo);

    document.getElementById('gcdVal').textContent = gcd;
    document.getElementById('lcmVal').textContent = lcm > 1e15 ? '> 10¹⁵ (overflow)' : lcm;
    document.getElementById('resultGrid').style.display = '';

    if (gcd === 1) document.getElementById('coprimeNote').style.display = '';

    // Steps
    const facts = nums.map(n => primeFactors(n));
    const factLines = nums.map((n,i) => `${n} = ${factStr(facts[i])}`).join('\n');
    document.getElementById('factStep').textContent = factLines;

    // GCD: min powers of primes in ALL numbers
    const allPrimes = new Set(facts.flatMap(f => Object.keys(f)));
    const gcdPrimes = {};
    allPrimes.forEach(p => {
      const inAll = facts.every(f => f[p]);
      if (inAll) gcdPrimes[p] = Math.min(...facts.map(f => f[p] || 0));
    });
    document.getElementById('gcdStep').textContent = `GCD = ${factStr(gcdPrimes)} = ${gcd}`;

    // LCM: max powers
    const lcmPrimes = {};
    allPrimes.forEach(p => { lcmPrimes[p] = Math.max(...facts.map(f => f[p] || 0)); });
    document.getElementById('lcmStep').textContent = `LCM = ${factStr(lcmPrimes)} = ${lcm > 1e15 ? '(very large)' : lcm}`;

    document.getElementById('stepsSection').style.display = '';
  }