Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

2 Answers 2

up vote 1 down vote accepted

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

share|improve this answer
1  
See my answer and the comment by Amzoti... –  Martín-Blas Pérez Pinilla Apr 5 at 22:49
add comment

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

share|improve this answer
    
I do not understand why useless? –  zighalo Apr 5 at 22:42
    
Try to use some... –  Martín-Blas Pérez Pinilla Apr 5 at 22:47
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.