Most people are familiar with the concept of a prime number, but often it's defined and used rather loosely.
**1** a prime?
*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.*

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.

See also LanguageComparisonFramework CategoryMath

- Here's the usual definition
**A prime number is a number divisible only by itself and 1.**

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

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

- 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*.

- There are a lot of them.
- Every positive number can be written as the product of primes uniquely, up to the order of the primes.
- 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. - 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?

- Define a sequence with q[1]=0, q[2]=2, q[3]=3, and q[n]=q[n-2]+q[n-3].

- 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.

- Yes - early ones, with a few exceptions, are the product of two primes, say
- Are there infinitely many PrimePairs?
- This is a well-known OpenQuestion. The experimental evidence suggests yes.

- 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"}

- 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

View edit of April 24, 2011 or FindPage with title or text search