4 ms·
How about the prime number problem. It's simple enough to understand. "A prime number (or a prime) is a natural number greater than 1 that has no positive divi
by iamcreasy 10y ago
How about the prime number problem. It's simple enough to understand.
"A prime number (or a prime) is a natural number greater than 1 that has no positive divisors other than 1 and itself. There are infinitely many primes, as demonstrated by Euclid around 300 BC. There is no known simple formula that separates prime numbers from composite numbers."
- williamstein 10y agoWhere are you quoting this from? It's ill-defined / ambiguous as you're stating it. I'm a professional number theorist and I don't understand what your question is actually asking. Thanks!
- hilop 10y agohttps://en.wikipedia.org/wiki/Prime_number https://en.wikipedia.org/wiki/Prime_number please improve the article :-)
- iamcreasy 10y agoI quoted it from Wikipedia. The problem is the last line. There is no known simple formula to identify prime numbers. Could you provide more clarification on what's wrong?
- williamstein 10y agoWhat is a "simple formula"? I have no idea what "simple formula" means. In math reseacrch everything must be 100% precise and well defined.
- tf2manu994 10y agoI think they mean something a great deal faster than just dividing by each number to check.
- SAI_Peregrinus 10y agoAKS is a primality check in polynomial time, IE much faster than trial division. It's not "simple" for certain values of simple, but it's only 5 major steps.
- iamcreasy 10y agoYou are correct, but I wrote it in context of the posted article.
- cyphar 10y agoI think they meant there's no equation that generates nothing but primes.
- deleted 10y ago[deleted]
- cyphar 10y agoFinding primes is a P problem though, so I'd consider it a "solved problem". There's no equation that generates nothing but primes, is that what you meant?
- iamcreasy 10y agoYes, kind of.
- YomiK 10y agoThere are many such formulas, such as Willan's 1964 simple formula for the nth prime. But they are basically all hiding a sieve, Wilson's theorem, the prime count function, or some other calculation. That is, none of them are at all practical, and most offer no insight. I'd recommend perusing "Formulas for Primes" by Underwood Dudley, 1983. Free online link: http://www.maa.org/programs/faculty-and-departments/classroom-capsules-and-notes/formulas-for-primes http://www.maa.org/programs/faculty-and-departments/classroo...