Prime Number

Most people are familiar with the concept of a prime number, but often it's defined and used rather loosely.

Here's the usual definition

A prime number is a number divisible only by itself and 1.

Technically, based on that definition, the only prime number is -1, since every other number is divisible by -1. 2, for example, is not prime by this definition because it is divisible by 2, 1, -1 and -2.

Another try

A prime number is a positive whole number such that the only positive divisors are itself and 1.

Better, but by this definition is 1 a prime?

A prime number is a positive whole number that has exactly two distinct positive divisors.

This last definition "works", but in various contexts many theorems about primes remain true when 'prime' is replaced by 'prime or -1'. Unfortunately, there doesn't seem to be a standard term for an integer that is prime or -1.

Here's another

A prime number is a whole number p that is strictly greater than 1, and such that if p divides a product a*b then p divides at least one of a and b.

This definition works even in fields (and other algebraic structures) such as the ComplexNumbers where there's no concept of "positive".

You can generate the integer primes using the SieveOfEratosthenes.

Prime numbers have some amazing properties, and you are invited to put your favorites here.

1. There are a lot of them.
2. Every positive number can be written as the product of primes uniquely, up to the order of the primes.
3. The number of primes less than or equal to n (defining pi(n), the PrimeCountingFunction?) is about n/ln(n). The value of pi(n)-n/ln(n) changes sign infinitely often.
4. This is a long one, but you are invited to try it for yourself.
   • Define a sequence with q[1]=0, q[2]=2, q[3]=3, and q[n]=q[n-2]+q[n-3].
     • The first few terms are q[4]= 2, q[5]= 5, q[6]= 5, q[7]= 7, q[8]= 10, and so on.
   • For what values of i is q[i]/i an integer?

Other questions include:

1. In the fourth example above there are non-prime values with the property mentioned. These are called Perrin pseudoprimes. Do they have any specific interesting properties?
   • Yes - early ones, with a few exceptions, are the product of two primes, say p and q, such that p-1 is an integer multiple of q-1.
     • Actually, this becomes less true as the pseudo-prime gets bigger, but it's then true in other interesting ways.

2. Are there infinitely many PrimePairs?
   • This is a well-known OpenQuestion. The experimental evidence suggests yes.

3. Are there interesting properties of the various non-prime numbers between PrimePairs?
   • Yeah -- they're even. Oh, /interesting/ properties ... no, other than that each of them, miraculously enough, lies between two primes -- in fact, two paired primes!

---

A typical problem to compare programming languages is to compute the first 1000 prime numbers, or the first one million prime numbers, as on SieveOfEratosthenesInManyProgrammingLanguages.

• To compare programmers, more likely. What sort of person would use this as a judgment about programming languages, when it's easy enough to write such a program in even the worst languages: $n=1000000;for($t=3;$t*$t<$n;$t+=2){if(!$c[$t]){for($s=$t*$t;$s<$n;$s+=$t*2){$c[$s]++}}};print "2\n";for($t=3;$t<$n;$t+=2){$c[$t]||print "$t\n"}

However, the SieveOfEratosthenes is not effective for finding the large primes (greater than ~10,000,000,000) that people are looking for these days. For such things, ProthsTheorem? is one of several useful tools (see http://www.utm.edu/research/primes/).

• Actually, primesieve, an "Optimized sieve of Eratosthenes implementation" at http://code.google.com/p/primesieve/, shows all primes below 100 billion counted (4,118,054,813 of them) in under 23 seconds (as of Apr 2011).

---

See also LanguageComparisonFramework

CategoryMath