Distribution of prime numbers. Can one find all prime numbers?

Question

I want to know if it is possible to find a formula that gives all the prime numbers? or can one find the distribution of prime numbers?

I know that there is a set of ongoing research on prime numbers. I know that there is already lot of results in prime numbers, the gap between primes, a lot of theorems starting from Euclid's one. My question is simple: Is it possible for someone to find explicit formula that gives all prime numbers (explicit function $f(x)$ is a prime for any natural number $x$)? or that gives the distribution of them? If it is not possible. Suppose that someone prove that factoring is an easy problem. Still not possible?

I mean, is there a theorem, logic, something that says that it is impossible to get all the primes or that all primes can be calculated based on condition $1$, $2$, $\dotsc$?

I hope that I make my question clear. I hope that it is a valid question.

Thank you very much for your help. Any reference or ideas would be appreciated.

Answer 1

We know that if $B$ is an infinite set, but countable, and $A \subseteq B$ is also infinite, then $A$ is also countable.

We know that if two sets have the same cardinality, then there is an ismorphism between them, meaning there is a function that is both injective and surjective between the 2 sets.

Euclid's proof has shown that there are infinite amount of primes. since the primes are a subset of the natural numbers, and $card(\mathbb N) =\aleph_0$, we know that if $P$ is the set of all prime numbers, $card(P)=\aleph_0$.

Combining these 2 statements give us that there is a bijective function from the natural numbers to the primes.

So theoretically, yes, there is such a function that gets a natural number $k$ and will give you the $k-th$ prime.

However, such a function was not yet found...

Answer 2

There are explicit formulas for the $n$-th prime... but they are useless. See Prime Formulas in MathWorld.

Answer 3

An algebraic formula resolving to the (n+1)th Prime number was first discovered by A.Venugopalan in the year 1983. This formula among other formulas were published in the Proceedings of the Indian Academy of Sciences(Math. Sci.), Vol.92, No.1, September 1983 pp 49-52. The formula is shown below:

$$P_{n + 1}^2{\rm{ = 1 + }}\left| {{\rm{ }} - {{\log }_X}\left( {\raise.5ex\hbox{$\scriptstyle 1$}\kern-.1em/ \kern-.15em\lower.25ex\hbox{$\scriptstyle 2$} {\rm{ }}\sum\limits_{{a_1} = 1}^{{p_1} - 1} {...\sum\limits_{{a_n} - 1}^{{p_n} - 1} {\sum\limits_{b = 1}^n {{X^{ - {{\left( {\sum\nolimits_1^n {{a_i}{Q_i} - bQ} } \right)}^2}}}} } } - {\rm{ 1/X }}} \right)} \right| % MathType!MTEF!2!1!+- % feaagKart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn % hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr % 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0dg9Lq-Fc9 % vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x % fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamiuamaaDa % aaleaacaWGUbGaey4kaSIaaGymaaqaaiaaikdaaaGccaqGGaGaaeyp % aiaabccacaqGXaGaaeiiaiaabUcajqgaacGaaeiiaOWaaqWaaKazaa % sabaGaaeiiaiabgkHiTiGacYgacaGGVbGaai4zaOWaaSbaaKazbaka % baGaamiwaaqcbaAabaGcdaqadaqcKbaWaeaajqgaaeaeaaaaaaaaa8 % qacaGG9cGaaeiiaOWaaabCaeaacaGGUaGaaiOlaiaac6cadaaeWbqa % amaaqahabaGaamiwamaaCaaaleqabaGaeyOeI0YaaeWaaeaadaaeWa % qaaiaadggadaWgaaadbaGaamyAaaqabaWccaWGrbWaaSbaaWqaaiaa % dMgaaeqaaSGaeyOeI0IaamOyaiaadgfaaWqaaiaaigdaaeaacaWGUb % aaoiabggHiLdaaliaawIcacaGLPaaadaahaaadbeqaaiaaikdaaaaa % aaWcbaGaamOyaiabg2da9iaaigdaaeaacaWGUbaaniabggHiLdaale % aacaWGHbWaaSbaaWqaaiaad6gaaeqaaSGaeyOeI0IaaGymaaqaaiaa % dchadaWgaaadbaGaamOBaaqabaWccqGHsislcaaIXaaaniabggHiLd % aaleaacaWGHbWaaSbaaWqaaiaaigdaaeqaaSGaeyypa0JaaGymaaqa % aiaadchadaWgaaadbaGaaGymaaqabaWccqGHsislcaaIXaaaniabgg % HiLdqcKbaWa8aacqGHsislcaqGGaGccaqGXaGaae4laiaabIfajaa4 % peGaaeiiaaGcpaGaayjkaiaawMcaaaqcKbaaciaawEa7caGLiWoaaa % a!8140! $$

Answer 4

Asymptotically, the probability of prime is $1/\log(n)$. As n increases, a random integer n becomes less and less likely to be a prime.

Intuitively, in approximate terms, $1/2$ of numbers are eliminated as multiples of $2$; $1/3$ eliminated as multiples of $3$; $1/4$ eliminated as multiples of $4$... So the probability is $(1-1/2) * (1-1/3) * (1-1/4) * (1-1/5)$... for any prime less than $n$.