The least common multiple is the smallest nonnegative common multiple.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 | <?php declare(strict_types=1); // Least Common Multiple in PHP // // PURPOSE // The least common multiple is the smallest nonnegative common multiple. For positive inputs // it equals a divided by gcd(a,b), multiplied by b. // // METHOD // Handle zero first. Compute the gcd with Euclid, divide before multiplying to reduce // intermediate overflow, and return the product. // // COMPLEXITY // O(log(min(a,b))) arithmetic steps, O(1) auxiliary space. // // CONTRACT // Inputs are nonnegative. Returns 0 if either input is zero. The final product must fit the // integer range. // Public APIs infer array lengths except in C, which accepts pointer/length pairs. Vertex // counts and matrix dimensions remain explicit. Arrays must contain signed 32-bit integers. // Sorted order, correct tree topology, and caller-owned data-structure invariants are // preconditions; checking them on every query would change query complexity. // Scalar and shape checks are included. Value-range checks are included where needed to // prevent invalid indexing or nontermination. Allocation sizes are capped at 4,000,000 // workspace entries. Arithmetic outside Python raises an error on 32-bit overflow; Python // uses arbitrary precision. Native allocation failures propagate. In-place outputs may be // partly updated after arithmetic failure. These are single-threaded, in-memory // implementations. // // LANGUAGE DETAILS // PHP 8.1+ on a 64-bit runtime: packed arrays, strict scalar types, read-only inputs by // value using copy-on-write, references only for outputs, and checked 32-bit arithmetic. // Invalid input and overflow throw exceptions. PHP arrays have higher overhead than native // packed buffers in C/Java. // // EXAMPLE // Expected return: 36. // Run: php example.php // Tests for this exact source artifact run before publication. The accompanying source // archive includes unit cases, runtime results, and source hashes. function alg_require(bool $valid): void { if (!$valid) throw new InvalidArgumentException("invalid algorithm input"); } function alg_checked(int|float $v): int { if ($v < -2147483648 || $v > 2147483647 || floor($v) != $v) throw new OverflowException("32-bit result overflow"); return (int)$v; } function alg_add(int $a,int $b): int { return alg_checked($a+$b); } function alg_sub(int $a,int $b): int { return alg_checked($a-$b); } function alg_mul(int $a,int $b): int { return alg_checked($a*$b); } function alg_size(int $n): int { alg_require($n>=0 && $n<=4000000); return $n; } function lcm(int $a, int $b): int { alg_require((($a >= 0) && ($b >= 0))); if ((($a == 0) || ($b == 0))) { return 0; } $x = $a; $y = $b; $remainder = 0; while (($y != 0)) { $remainder = ($x % $y); $x = $y; $y = $remainder; } return alg_mul(intdiv($a, $x), $b); } $a = 12; $b = 18; $result = lcm($a, $b); echo $result, PHP_EOL; |