Category: Number Theory
Euler’s totient function
Rabin-Miller’s Test for Primality
Chinese Remainder Theorem
GCD, LCM and Euclidean Algorithm Extended
Sieve of Eratosthenes
Sieve of Eratosthenes is a wonderful technique to get a list of prime numbers in the range (1, n]. It also supports testing for primality of any number in O(1) after pre-processing. The pre-processing phase has time complexity in original version and in enhanced version. Original Sieve of Eratosthenes This technique relies on one simple observation: if x is a composite number (or we can say: if x is not a prime number), then there exists a prime number p which is a divisor of x, and of course, p < x. So, if for every prime number p such … Continue reading Sieve of Eratosthenes
Introduction to Prime Numbers
I. What is a Prime Number? A number is called prime if it satisfies all the following conditions: is a natural number, greater than 1, has only 2 divisors: 1 and itself. For example, are the first prime numbers. If so, what is NOT a prime number? not a natural number (e.g. a fraction, like or ), less than or equal to 1 (e.g. -3, 0, 1 are NOT prime), can be formed by multiplying 2 natural numbers less than itself (e.g. is NOT a prime number). II. Why is Prime Number important? In the modern world, prime numbers are … Continue reading Introduction to Prime Numbers