- #1
clint222
- 36
- 0
Hello!
This question may seem silly. I'm a first year engineering and computer science student, not a mathematics student. I have only recently become interested in prime numbers, factorization algorithms, and prime number finding algorithms. I know only extremely elementary number theory, so forgive my ignorance.
I understand the idea behind the Sieve of Eratosthenes, and I realize that there are a variety of similar but more efficient, based on the same general idea.
I had been interested in the idea that a function for the nth prime exists. That is, a function which could be used to directly all of the prime numbers. For example, something of the form p(n), where p(1) = 2, p(2) = 3, etc. I mean one that doesn’t require knowing all of the primes before n, like integer sieves require.
A number theory textbook I have says that no such function has ever been found, and it is likely impossible for such a function to exist. It does discuss some recursive functions that can calculate the nth prime, but they are actually quite a bit less efficient to find prime numbers than a simple integer sieve.
I was wondering if there is any reason why a more efficient prime finding function is thought to be impossible. Or is it simply that evidence of such a thing hasn't been found so it probably isn't possible? I know that this type of function has been of interest for a very long time.
Thanks for helping me learn more about number theory!
Clint
This question may seem silly. I'm a first year engineering and computer science student, not a mathematics student. I have only recently become interested in prime numbers, factorization algorithms, and prime number finding algorithms. I know only extremely elementary number theory, so forgive my ignorance.
I understand the idea behind the Sieve of Eratosthenes, and I realize that there are a variety of similar but more efficient, based on the same general idea.
I had been interested in the idea that a function for the nth prime exists. That is, a function which could be used to directly all of the prime numbers. For example, something of the form p(n), where p(1) = 2, p(2) = 3, etc. I mean one that doesn’t require knowing all of the primes before n, like integer sieves require.
A number theory textbook I have says that no such function has ever been found, and it is likely impossible for such a function to exist. It does discuss some recursive functions that can calculate the nth prime, but they are actually quite a bit less efficient to find prime numbers than a simple integer sieve.
I was wondering if there is any reason why a more efficient prime finding function is thought to be impossible. Or is it simply that evidence of such a thing hasn't been found so it probably isn't possible? I know that this type of function has been of interest for a very long time.
Thanks for helping me learn more about number theory!
Clint