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]