Why is creating a comprehensive formula to find primes so hard to do?

no ELEGANT formula exists that gives the nth prime

The pedantic asshats above are technically correct, there do exist complete prime formulas but they're just tautologies. They don't actually do anything other than restate "the nth prime is the nth prime" in symbols.

Making a formula for primes requires knowledge of how primes behave. An exact formula would be equivalent to an exact knowledge of the distribution.
Since we have an asymptotic knowledge we can use the PNT to make pretty decent guesses, and there's also Mills' theorem which is just a cute trick on the fact that we know prime gaps aren't obscenely huge, but the primes are too random to be both precise and complete.

Idiot here, would there be any significant mathematical or practical applications/implications of figuring out exactly how primes work?

I too am an idiot but I heard large primes are used in crypography, if you knew how to generate prime you could probably crack a lot of encryptions
>idk any details

Not him but supposed you have a formula for the nth prime, [math] f(n) = p_n [/math]. Then [math] \pi(f(n)) = n [/math]. This implies that [math] f(n) [/math] is (in some restricted sense) the inverse of the prime counting function. Therefore the complexity of this [math] f [/math] is linked to the complexity of the prime counting function itself. And what do we know about the prime counting function? We know that the prime counting function cannot be a rational function. So f is the inverse of a non-rational function. Then I am sure that if you consider the other simple cases for algebraic functions you can prove that the prime counting function can't be of that type. So we can very easily establish that the prime counting function itself is a very weird function, not easily expressible in the language of algebra. Ugly, in other words. And f is the inverse of whatever ugly mess the prime counting function is, which will be an even uglier mess. Therefore it has been proven that f will be an ugly mess.

Pretty obvious there would be huge mathematical effects if prime numbers were effectively solved considering this is 99% of what number theorists do with their time.
Practical effects are unlikely. The only place primes really show up is cryptography and factoring numbers is a different topic than predicting the nth prime.

> if you knew how to generate prime you could probably crack a lot of encryptions

It depends. I think having a formula for the nth prime would be better for those making encryption algorithms than for those trying to crack them. Algorithms usually want to find two large primes, multiply them and then use the resulting number as protection. And to get past the protection you need to know the two primes. If you are just given the number it is incredibly difficult to find what the two primes that divide it are. Extremely time-consuming.

Having a prime formula would make it easier for algorithms to generate these large primes. And it would mean that we could "easily" generate arbitrarily large primes to aid us when computers keep getting faster and faster so bigger and bigger primes are needed to ensure security.

If you are a hacker trying to crack the code and all you have is a formula for primes then what are you really going to do? The best you can do is try to guess the magnitude of the primes and then use the formula to generate a list of possible prime factors of the big number but then that is not too different from what we have today. It is not like banks have super secret primes. The primes they have the hackers have too. So nothing would change for hackers.

Yeah but what if you were the only one with the formula duh

now THIS is the kind of masterful bait that sci deserves

It's not, a teenager could write one, here's a simple example:

Take n, check if prime by division, increase n by 1.
repeat.

I believe OP is referring to a non brute force method.

for (int x = 3; x

wait I messed up, oh well, you can figure it out

>They don't actually do anything other than restate "the nth prime is the nth prime" in symbols.
Wrong.

>didn't google it: example post

Newton raphson method or whatever works nicely and is easy to program.

That's an algorithm, not a formula