Maths Algorithms in TheAlgorithms/Python

Trial division up to the square root is the standard primality test. This implementation sharpens it with the 6k observation. After handling 0, 1, 2, and 3 as special cases, the code eliminates all even numbers and all multiples of 3 in a single guard. These two checks remove two-thirds of all integers from consideration. Every integer falls into one of six residue classes modulo 6; residues 0, 2, 3, and 4 are always composite, leaving only residues 1 and 5 as candidates. The loop steps by 6 and checks both i (the 6k minus 1 position, starting at 5) and i + 2 (the 6k plus 1 position) per iteration. This cuts loop iterations to roughly one third of naive trial division. The doctest confirms that 563 and 2999 are prime while 27, 87, and 67483 are not.

The standard Euclidean algorithm computes GCD for exactly two numbers. This implementation extends GCD to an arbitrary number of inputs by factoring each number into its prime components using a Counter object, then intersecting all Counters. Python's Counter & operator returns common elements with the minimum count, which corresponds exactly to the lowest exponent of each shared prime factor across all inputs. For example, GCD(18, 45) becomes Counter({2:1, 3:2}) intersected with Counter({3:2, 5:1}), yielding Counter({3:2}), whose product is 9. The variadic *numbers parameter allows any number of arguments, making this a genuine n-way GCD. The doctest shows that GCD of all integers from 1 to 10 is 1, as expected when 1 is in the set. Non-integer or negative inputs raise an exception through the get_factors helper.

The maths/fibonacci.py file contains seven different Fibonacci implementations for benchmarking: iterative with yield, iterative with a list, recursive, memoized recursive, and a matrix exponentiation method. This iterative version demonstrates the canonical approach. It starts the sequence at [0, 1] and appends fib[-1] + fib[-2] exactly n - 1 times. The two boundary conditions handle n = 0 (return a single-element list) and negative inputs (raise ValueError). The loop has no branching: each iteration is a single list append. The result is O(n) time and O(n) space. The matrix exponentiation variant in the same file computes the nth Fibonacci number in O(log n) time, which is the preferred approach for very large indices. The doctest file also covers the generator variant in fib_iterative_yield, which yields values lazily rather than accumulating a list.

Euclidean distance in two dimensions is the hypotenuse of a right triangle: the square root of the sum of squared differences in each coordinate. The formula extends directly to any number of dimensions by summing squared differences across all dimensions before taking the square root. The numpy implementation collapses all of this into one expression. np.asarray converts lists and tuples to arrays without copying when the input is already an array. The subtraction, squaring, and np.sum all broadcast across dimensions automatically. The no-numpy variant euclidean_distance_no_np directly below uses a generator expression with zip to pair and square corresponding coordinates, then raises the sum to the power of one half. The file's benchmark function in __main__ shows that the numpy version is faster for large vectors despite the conversion overhead. The doctests confirm consistent results across 2D, 3D, and 4D inputs.

Computing 3 to the power of 13 by repeated multiplication requires 12 multiplications. Binary exponentiation does it in 5. The algorithm reads the exponent in binary from least-significant to most-significant bit. The bitwise AND on line 81 checks whether the current bit is 1: if it is, the accumulated result is multiplied by the current power of the base. The base is squared unconditionally each iteration, and the exponent is right-shifted by one, which is equivalent to dividing by 2. After processing all bits, res holds the answer. For 13 in binary (1101), the algorithm multiplies res by the base at positions corresponding to the three set bits, squaring the base between each. The technique extends to modular exponentiation: binary_exp_mod_iterative in the same file applies the modulus at each step to prevent overflow when computing large powers used in RSA and Diffie-Hellman key exchange.

The Chinese Remainder Theorem guarantees that a system of congruences with coprime moduli has a unique solution modulo the product of the moduli. Finding that solution requires modular inverses, which the extended Euclidean algorithm provides. The standard Euclidean algorithm returns only the GCD; the extended version also returns Bezout coefficients. For coprime inputs the GCD is 1, which means one coefficient is the modular inverse of the first input modulo the second. The recursive structure follows standard Euclidean reduction and reconstructs coefficients on the way back up from the base case. The chinese_remainder_theorem function uses these coefficients to build the combined solution and takes it modulo the product of both moduli to land in the canonical range. The doctest confirms that 31 is the smallest positive integer leaving remainder 1 when divided by 5 and remainder 3 when divided by 7.