The issue is input size. The running time is expressed as a function of the input size. While you have an “n” in your head, that “n” is not the input size. Change the “n” in your head to an “m” and then rethink it.
(Note that we fudge things sometimes for convenience. For nxn matrices we express things in terms of “n” instead of the more correct “n[sup]2[/sup]”. So matrix addition is linear time rather than quadratic.)
Dude, you haven’t written that article yet 
on further investigation the last ) get’s lost when clicking on your link using Firefox.
Interesting flaw in VB there. I just cut and pasted the URL and put it on a line of its own. VB is supposed to automatically insert the tags. We would report the flaw to ???
It appears to be confused by the use of parentheses in the URL
What are the URL standards anyway?
We are getting way off topic, but according to RFC 1738 Uniform Resource Locators (URL), that url is illegal because ( and ) are “unsafe” characters and “All unsafe characters must always be encoded within a URL.”
The correct representation of that url is: http://en.wikipedia.org/wiki/NP_(complexity)
The replies thus far have been limited to mathamatical applications. I’m aware of some applications in the machine trades where understanding of primes is useful.
For example, when making a gear, a dividing head is used to index the blank for each tooth. If the required number of teeth (N) is NOT prime, then N can be factored, and a the gear generated by a fairly limited set of indexing plates. The indexing plates are a circle with various numbers of holes around them. While not all the indexing plates have prime numbers of holes, there MUST be a plate for every prime, or there will be certain numbers of teeth that can’t be generated. A typical set of indexing plates won’t generate any prime number of teeth beyond 100. 127 (prime) tooth gears are needed to convert imperial machines to cut metric threads, and vice versa. In order to generate these gears, a 127 hole indexing plate is required.
Another gearing application is hunting ratio gear sets. Suppose you have a 10T gear driving a 20T gear. Each tooth on the 20T gear will always be driven by the same tooth on the 10T gear, and each on the 10T gear will drive only 2 teeth on the mate. This will be noisy, and once broken in must be reassembled to the same phasing, or it will be REALLY noisy.
If instead we used gears with 11 and 23 teeth, we’d have nearly the same gear ratio, but now every tooth eventually drives every other tooth. This equalizes wear, and results in quiter operation after breakin…eventually all the teeth aquire exactly the same shape. This is known as a “hunting ratio”.
It is possible to have hunting ratios with non-prime gears, however, the condition is that the two gears don’t have any common prime factors. Again, primes. If you look at gear ratios used on car axles, many ofl the common ones are a ratio with at least one prime. Similarly, the gear ratios in transmissions are often designed to include prime numbers of gear teeth.
Note that primes are useful in gearing but not required. Every four-stroke engine has a 2:1 set of timing gears, and since this can’t be a hunting ratio, there is no reason to prefer that the smaller gear be prime. (assuming an idler gear is not used)
The infinitude is incidental. There are rings (sets with notions of addition and multiplication like the integers) with only finitely many elements, and they certainly have only finitely many primes (or, more precisely, prime ideals).
As for why it’s fundamental, let me restate it in more elementary terms. 0 mod p is a multiple of p. So, if ab = 0 mod p, then ab = kp in the integers, thus p | ab (p divides ab).
Now, we can take the “doesn’t have any nontrivial divisors” definition and prove that:
if p | ab, then p | a or p | b
This means that for ab to be divisible by p, either a or b must already be a multiple of p. It turns out that this condition can also be used to prove the “normal” definition, and further it can be applied in many more general situations than the integers.