Abstract
- An positive integer whose divisor is
1
and itself, and itself cant be1
- 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
- States that every integer greater than 1 can be represented uniquely as a product of prime numbers
- Prime Number (质数) is like the atomic Factor in this case, and thus adhere to Factor Maximum Value
Applications
Prime Number Verification
Verifying if an Integer (整数) is a Prime Number (质数) in O(sqrt(n))
i <= Math.sqrt(n)
because prime number is a Factor, see Fundamental Theorem of Arithmetic
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
Theorem
Set of Primes is Infinite
- There is an infinite number of Prime Number (质数)
Terminologies
Co-prime
- We call 2 Integer (整数) co-prime iff the only common Factor between these two numbers are
1