Maths and Computing:

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 x_n be the product of the all the prime numbers up to the nth prime number, p_n. The number (x_n + 1) is either prime of has a prime factor that is greater than p_n.

List of Primes

Primes generated using the prime sieve of Eratosthenes

List of primes

The prime sieve of Eratosthenes

Generating primes to a maximum value of n

Example: primes between 1 and 100

Square root of 100 is 10

Special Primes

A list of primes that have a specific format

Mersenne Primes

Primes of the form 2^p - 1 (p is always prime)

1: 2¹ - 1

3: 2² - 1

7: 2³ - 1

31: 2⁵ - 1

127: 2⁷ - 1

8191: 2¹³ - 1

131071: 2¹⁷ - 1

524287: 2¹⁹ - 1

2147483647: 2³¹ - 1

Fermat Numbers

Primes of the form 2ⁿ + 1 (n is always a power of 2)

3: 2¹ + 1

5: 2² + 1

17: 2⁴ + 1

257: 2⁸ + 1

65537: 2¹⁶ + 1