- Greatest Common Factor
def GCF(a,b): while b: a,b = b, a%b return a
This uses a method called Euler's Method, meaning GCF(a,b) equals GCF(a, a mod b).
- Least Common Multiple
Although the least common multiple of two numbers can be expressed as the product over the gcf, to write it in python it would be:
def LCM(a,b): a,b = sorted([a,b]) array = list(range(a,a*(b+1), a)) #[b, 2b, 3b, 4b, 5b, ..., ab] return min(list(filter(lambda x: x%a, array)))
So, the max LCM is a * b, and the minimum is b. By making a list of multiples of b, that reduces the length of the list of multiples, thus reducing the amount of numbers to check. This algorithm is pretty fast, but it makes more sense to do (a*b)/gcd(a,b).
- Prime Checker
def prime(a): if a%2 == 0 and a > 2: return False for i in range(3,int(math.sqrt(a)) + 1, 2): #Or, you could do int(a ** .5) if a%i == 0: return False return True
As opposed to checking from 2 to the square root, it checks 2, then 3, then 5, ... up to the square root. Before, I created an algorithm which did all of the prime numbers up until the square root, but the number had to be VERY large for that method to be faster than the one above.
- Product of a List
Unlike the ones above, this one uses a module functools, and the function reduce. What that function does, is it reduces the entire list into an element by doing a binary operation.
def product(array): return functools.reduce(lambda x,y: x * y, array)
What this does is brings it together by multiplying the numbers in the list. So the list becomes ((((a*b)*c)*d)*e). Now, the list is reduced to one element.
I'll update this post as I think of other functions to add.