Abstract


  • An positive integer whose divisor is 1 and itself, and itself cant be 1
  • 2 is the smallest prime number
  • We can check if an integer is prime by checking if it has any divisor that is between 2 and itself

Fundamental Theorem of Arithmetic

Applications


Prime Number Verification

Verifying if an Integer (整数) is a Prime Number (质数) in O(sqrt(n))

public static boolean isPrime(long n) {
  if (n <= 1) return false;
  for (long i = 2; i <= Math.sqrt(n); i++) {
    if (n % i == 0) return false;
  }
  return true;
}

Prime Number Generator

We can obtain the next prime of a given integer by keep incrementing the given integer and perform Prime Number Verification until we obtain a prime number

public static int nextPrimeGenerator(int currPrime) {
    int nextPrime = currPrime + 1;
    while (!isPrime(nextPrime)) nextPrime++;
    return nextPrime;
}

Theorem


Set of Primes is Infinite

Terminologies


Co-prime