Integer Bounds

• Most languages have a 32-bit integer type (Int) and a 64-bit integer type (Long).
  • Most computers use 64-bit processors, so you’ll probably never need more than 64-bits to store a number.
• Java
  • Int = 32-bits
  • Bounds of Int = -2^32 to 2^32
• Python
  • Python is not statically typed, so a lot more functionality is handled implicitly.
  • Ints are unbounded in Python. It will allocate more memory as you use a larger number

Prime Numbers

• A prime number is a number that:
  1. Is larger than 1
  2. Is only divisible by itself and 1.
• List of primes: 2, 3, 5, 7, 11, 13, 17, 19, …
  • There are infinitely many prime numbers

Prime Factorization

• Any integer can be broken down into a product of every prime number. This is called the prime factorization.

    ![PrimeFactorization.png](<https://s3-us-west-2.amazonaws.com/secure.notion-static.com/1810d966-7732-4f34-8496-a935bd9f3185/PrimeFactorization.png>)
  

• Example: $1050 = 2^13^35^27^111^013^017^0...$

  • Every prime can be included. Some will have a 0 exponent.
  • The more times a number appears in the prime factorization, the higher the exponent is. 5 appears twice.

• A prime number’s prime factorization will look like:

  • $13 = 2^03^05^07^011^013^1$

Divisibility

• Composite numbers are divisible by some prime numbers.
• Prime numbers are only divisible by themselves (and 1)
• To find out if one number is divisible by another:
  • Method 1: Do modulus division. If the result (remainder) is 0, they are divisible.
    • 10 % 5 = 0
  • Method 2: Compare their prime factorizations.
    1. Find the prime factorization of each.
    2. If A’s prime factorization contains every base in B’s prime factorization, A/B divides cleanly.
    • Example: 100, 20
      • $100 = 2^25^2$
      • $20 = 2^25^1$
      • 2 and 5 are in both, so 100 is divisible by 20.
• Finding the Greatest Common Denominator (GCD) and Least Common Multiple (LCM).
  1. Find the prime factorization of both numbers.
  2. GCD: For each base, take the lowest exponent including 0 exponents.
  3. LCM: For each base, take the highest exponent.
  • Example: 5, 10
    • $5=2^03^05^17^0$
    • $10=2^13^05^17^0$
    • $GCD(5,10) = 2^03^05^1 = 5$
    • $LCM(5,10) = 2^13^05^1 = 10$
• GCD(x,y) * LCM(x,y) = x*y
  • If you know one of them (GCD or LCM), you can use this formula to find the other.
  • Example: x = 5, y = 10
    • GCD(5, 10) = 5
    • LCM(5, 10) = 50/5 = 10.