Unix Meets Prime Numbers

Other than for their use in cryptography, prime numbers might not be on your list of favorite topics, but prime numbers have some very interesting qualities. It's probably been a while since you learned about them, but the definition is simple. A prime number is a natural (whole and non-negative, they are sometimes called "counting numbers") number greater than 1 that can only be divided (leaving no remainders) by 1 and itself. The smallest prime number is 2, but no other numbers divisible by 2 can be prime. So we start out with 2, 3, 5, 7, 11 and 13 and then move through to infinity. But how is Unix helpful?

For one thing, Unix systems generally have a command called factor that will show you the factors for a number -- the numbers that multiplied result in the number. If you use factor with a prime number, you get a single factor -- the number itself. If you use factor with a number that isn't prime, you get two or more factors.

$ factor 3
3: 3
$ factor 11
11: 11
$ factor 15
15: 3 5

Prime numbers are easy to recognize or "think through" if they're, say, under 50. Beyond that, it starts getting hard. Type "factor" on your command line and then start pounding on the numeric row of keys on your keyboard and you'll see something like this:

$ factor 7345934759783403485034239290
7345934759783403485034239290: 2 5 5651 21589 6021285687865665911

OK, definitely not intuitive. I wouldn't have been able to do that in my head! Factor 6021285687865665911, on the other hand and you'll see this:

$ factor 6021285687865665911
6021285687865665911: 6021285687865665911

In fact, every factor for any number is prime; otherwise it would be factored further. Doesn't this kind of thinking make you miss middle school?

Using the factor command, you could then easily write a script to determine if a number if prime or not. You just have to count the factors. Since factor's output consists of both the original number and its factors, we're going to make use of the fact that any factor command output with only two pieces of text indicates the number is prime; otherwise it is not.

#!/bin/bash

if [ $# == 0 ]; then
    echo -n "enter a number> "
    read num
else
    num=$1
fi

numFacs=`factor $num | wc -w`

if [ $numFacs -gt 2 ]; then
    echo "$num is NOT a prime number"
else
    echo "$num is prime"
fi

When you run the script, you will see somethig like this:

$ ./isPrime 309327409273597
309327409273597 is NOT a prime number
$ factor 309327409273597
309327409273597: 11 13 2163128736179
$ ./isPrime 2163128736179
2163128736179 is prime

Using the factor command, as shown above, you can easily find some prime numbers -- both small and very large ones in fact.

$ factor 934794791791791273918739187391827391287392
934794791791791273918739187391827391287392: 2 2 2 2 2 449 15236758099 11820719401081 361229727778201

If you need to generate a group of prime numbers, you could use a script like that shown below, provide it with the upper limit for the primes you're interested in and sit back and watch. This script will take some time to run if you want all primes under a billion, but it works quickly with relatively small numbers.

#!/bin/bash

limit=$1
sieve="$(seq 2 $limit | sort)"

for n in 2 $(seq 3 2 $limit)
do
  sieve="$(comm -23 <(echo "$sieve") <(seq $(($n * $n)) $n $limit|sort))"
done

echo "$sieve"|sort -n

Try it out and you'll see a list of numbers in order thanks to the numeric sort at the bottom of the script.

$ ./sieve 1000
2
3
5
7
11
13
17
19
23
29
31
37
...
911
919
929
937
941
947
953
967
971
977
983
991
997

I call this particular script "sieve" after the Sieve of Eratosthenes that it implements.  This "sieve" defines a method of identifying prime numbers.  It works by setting up a range of numbers and then ruling out all those that are multiples of any of the smaller numbers. For example, between 1 and 100, we can rule out all numbers that are multiples of 2 (except for 2 itself), multiples of 3 that aren't already ruled out, multiples of 5 that aren't already ruled out, and so on. You can find a reference to the Sieve of Eratosthenes at this URL.

Sieve_of_Eratosthenes

If you have a need for prime numbers, you might appreciate how easily they can be generated.  If not, maybe a little middle school math nostalgia isn't such a bad thing.