# Math

A few functions not included in Python's math class, GCD, LCM, Prime Number Detection, and Prime Factorization.

#!/bin/python import math #computes the greatest common divisor between two numbers def gcd(a, b): x=a y=b while y!=0: r=x%y x=y y=r return x #computes least common multiple of two numbers def lcm(a, b): c=gcd(a, b) return a*b/c #determines if a number is prime or not def isPrime(num): if num%2==0: return False maxnum=math.floor(math.sqrt(num)) i=3 while i<=maxnum: if num%i==0: return False else: i+=2 return True #returns a list of all the prime factors of a number def factorize(num): if isPrime(num): return [num] maxnum=int(math.floor(math.sqrt(num))) if gcd(num, 2)>1: ans=[2] return ans+factorize(int(num/2)) for x in range(3, maxnum+1, 2): if not isPrime(x): continue if gcd(x, num)>1: ans=[x] return ans+factorize(int(num/x)) #returns the nth fibonacci number def fib(n): a, b = 0, 1 for i in range(n): a, b = b, a + b return a #get list of fibonacci numbers def getFibs(n): a, b = 0, 1 l = [a, b] for i in range(n): a, b = b, a + b l+=[b] return l #returns the number of combinations n C r def nCr(n, r): return math.factorial(n)/(math.factorial(r)*math.factorial(n-r)) #returns the number of permutations n P r def nPr(n, r): total = 1 for x in range(0, r): total *= n-x return total #returns true if the string or number is a palindrome def isPalindrome(x): x=str(x) for y in range(0, len(x)/2): if(x[y]!=x[-y-1]): return False return True #the classic 3n+1 problem def collatz(n, memory={1:1}): if not n in memory: memory[n] = collatz(3*n+1 if n%2 else n/2, memory) + 1 return memory[n]

This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

Download this code in plain text format here