Prime Territory

The Prime Numbers are one of the most interesting topics in mathematics. Primes appear to be the building blocks of multiplication—you can express all positive integers as a unique set of primes factors—but there is not a simple equation to generate a list of primes, nor is there a simple way to determine if any given number is prime.

Given an integer n, the only way to determine if it is prime is to try to divide it by every prime between 1 and the square root of n. If you don't have a handy list of primes available, then you have to divide n by every number from 1 to the square root of n.

The calculation of primes takes a great deal of computing time. As such, primes number theory provides a rich ground for computer scientists to hone their skills. By learning how to create computer programs to calculate and store large sets of prime numbers, students learn the skills needed to handle large sets of other complex data.

Not only are primes good for play, it turns out that prime numbers are extremely important in the area of cryptography. Using prime numbers we can encrypt, and most importantly, decrypt data.

Although we think of the primes as building blocks, the series itself appears to be transcendental. That is, there does not appear to be a simple algebraic formula for calculating the list of all primes. We need to come up with other mechanisms for discussing primes. In this series of essays, I take different looks at different ways of investigating primes and computer programs to generate lists of primes.

Negative Space

The definition of prime numbers is a bit strange. We tend to think of definitions in the affirmative. A definition tells us what something is. We define a prime number as what it is not. A prime is not a composite. A composite is the product of two or more integers greater than one. A prime is a number that is not the product of anything except itself and 1. A prime has no divisors other than itself and 1.

You determine prime numbers by the process of elimination. The way you determine if the number n is prime is to see if you can divide it by any number between 1 and n/2. Proving that a given 14 digit number is prime involves several trillion operations.

Rather than trying to find out if a particular number is prime, it is quicker to find out which numbers are composites. The prime numbers are everything left over. The most popular way to discover prime numbers is with prime sieve. The most famous prime sieve is the Sieve of Eratosthenes. This sieve lists numbers in sets of six or twelve so that it is easy to remove common multiples. The Sieve of Eratosthenes was popular because you can perform it easily on a chalkboard or piece of paper.

Today we use computers, and should develop sieves optimized for computers. This web has a small number of articles geared toward creating a database of primes. The article discusses fun topics like the twin prime and Goldbach's conjectures.  The table of contents lists the articles with a brief summary. Feel free to skip around. I begin the article with a brief note on factoring, people interested in the meat of the argument might skip to the binary strings or prime patterns articles. 

Table of Prime Contents:

Factoring and Prime Components

Before jumping into primes, I should talk a little about the art of factoring. All integers can be broken into unique groups of prime factors. For example, the prime factors or 12 is [2,2,3]. Note 2*2*3=12.  Each unique group of factors produces a unique result. Note, the prime factors of a prime number is simply itself. We can write the first twelve numbers as prime factors:

{1, 2, 3, 2*2, 5, 2*3, 7, 2*2*2, 3*3, 2*5, 11, 2*2*4}

You notice, of course, that sometimes a factor gets repeated. For example 8 has the factors 2*2*2. Some times mathematicians write this as 23. The might write the prime factors of 24 as 23*3. (more)

A Discrete Prime Sieve

Rather than trying to find out if a given number is prime. I think it is easier to calculate all of the prime numbers, put them in a database and look them up as needed. To create such a list of prime numbers, you will want to make a prime sieve. In the simplest sieves, you start by crossing out all the numbers that are divisible by two, then all the numbers divisible by three.

Hey, wait a second, there is an infinite number of even numbers. This method isn't quite so simple because you could never complete the first step.

I wasted my youth developing discrete prime sieves. These sieves produce sets of primes in finite steps. This first essay shows a somewhat odd discrete prime sieve. I use a more advanced sieve in the essay on prime patterns. (more)

Binary Strings

The goal of this article is to create a large database that holds all the prime numbers. I find the easiest way to encode such a table is to store the primes as a long binary string. When we play with such a large binary string, we can see how the Goldbach and Twin Prime postulates are related. (more)

Prime Patterns

This is a more advanced sieve for filtering the primes. Again it is discrete, each iteration of the sieve filters out one prime and marks a group of integers as composites.

Descriptive Mathematics ~ Sponsors ~ Scribblings
© 2003 by Kevin Delaney