1

Is there a systematic scheme for identifying primes? For small numbers, it is easy to simply reproduce the whole prime, but for larger numbers, it seems like it could get cumbersome.

For instance, one could instead refer to the "$n$th" prime, but this is not much better since I suspect $n$ will also grow very quickly. It may also be the case that you know a number $x$ is a prime, but don't know how many primes are smaller than $x$.

Is there some sort of catalog of primes, which provides unique identifiers for each one?

Superbest
  • 3,400
  • 1
    Usually, primes are just indexed by their number. If you want a list, just google lists. For the number of primes less than $x$, this is $\pi(x)$ of the prime number theorem. – Michael Burr Jul 14 '15 at 01:47
  • No. The seeming randomness of the primes has for centuries been one of the lures hooking budding mathematicians on their future vocations. There is actually some regularity behind this randomness, but this leads into deep mathematics that is still being researched.

    There is no known simple and fast method for determining the $n$th prime, or as you astutely rephrased the problem, for determining the number of primes smaller than a given integer $x$.

     – Barry Smith Jul 14 '15 at 02:21
  • But there are:

    1. Simple methods for computing the $n$th prime that are quite slow when $n$ becomes large

    2. Faster methods for approximately computing the $n$th prime.

     – Barry Smith Jul 14 '15 at 02:23
  • @BarrySmith I'm not sure what you're characterizing as simple. Certainly the $n$th prime can be computed in $O(n^{2/3 + \epsilon})$ time, but I wouldn't call it simple. In theory it can be done in $O(n^{1/2 + \epsilon})$ time, but apparently this is not believed to be very effective in practice. But yes, this is still exponentially slower than estimates arising from PNT and refinements thereof. – Erick Wong Jul 14 '15 at 05:24

1 Answers1

0

The most common is exactly what you have said: the $n$th prime. There is no better way to denote primes because the primes are inherently difficult to formulate. There is good reason why a large part of modern number theory deals with the distribution of the primes: there is still so much we don't understand about the primes, let alone a simple way to express them.

As Michael Burr pointed out in the comments, if you want a list, you can find one easily online. For the number of primes less than $x$, this is $\pi(x)$ of the prime number theorem.

Clyde Kertzer
  • 2,904