Prime Numbers |
Prime Numbers
Properties of a prime number
Primes numbers are:
- Positive integers, greater than one
- Numbers that have only two distinct factors, 1 and itself
- Numbers that cannot be expressed as the product of two smaller integers
Determining if a number, n, is a prime
If the primes less n are known, then a check can be made to see if any of these primes are a factor of p.
If at least one of these primes is a factor, then n is not a prime, otherwise n is a prime number.
A more optimal test:
- Let q be the largest integer less than the square root of p
- Just the primes less than q are checked to see if they are factors of n
- If a prime, p, greater than q is a factor of n, then n/p is less than q and is prime or contains a smaller prime factor
Finding a list of the prime numbers less that n
This can be done by listing all of the natural numbers up to n and then removing all multiples of each prime as it is found,
starting with 2. This method is know as the prime sieve of Eratosthenes.
Facts about Prime Numbers
- 2 is the only even prime number
- There are infinitely many prime numbers
- There is no formula for the nth prime number
- Let xn be the product of the all the prime numbers up to the nth prime number, pn.
The number (xn + 1) is either prime of has a prime factor that is greater than pn.
List of Primes
Primes generated using the prime sieve of Eratosthenes
2,
3,
5,
7,
11,
13,
17,
19,
23,
29,
31,
37,
41,
43,
47,
53,
59,
61,
67,
71,
73,
79,
83,
89,
97,