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.

What is the best way to determine the prime numbers? Is there a way other than trial-and-error to determine them? Is the set of prime numbers finite or infinite?

share

migration rejected from mathematica.stackexchange.com Dec 14 '13 at 22:11

This question came from our site for users of Mathematica. Votes, comments, and answers are locked due to the question being closed here, but it may be eligible for editing and reopening on the site where it originated.

closed as off-topic by Bruno Joyal, Sam DeHority, Sujaan Kunalan, Nicholas R. Peterson, egreg Dec 14 '13 at 22:11

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Bruno Joyal, Sam DeHority, Sujaan Kunalan, egreg
If this question can be reworded to fit the rules in the help center, please edit the question.

    
Have you considered looking at the documentation? Something like typing `Prime and press F1? Prime –  Öskå Dec 14 '13 at 19:52
    
I am asking this because all algorithms I found are based on trial-and-error... Is there an other way to determine them? –  Claudia Dec 14 '13 at 19:53
3  
@Claudia You are asking a very, very, very well-researched question that mathematicians have grappled with for centuries. Mathematica is not going to solve this question for you. Wikipedia is a good start. –  Pickett Dec 14 '13 at 19:56
1  
There are infinitely many prime numbers. Mathematicians have been able to prove this since at least c. 300 BC where a proof was written in Euclid's Elements. Some call this theorem Euclid's Lemma. Your first question is not quite clear to me in light of this fact. –  J. W. Perry Dec 14 '13 at 20:55
    
Regarding your first question, there are many algorithms as you have probably seen in your research. In general they all involve some sort of "testing" procedure. As a result determining if a very large number is prime, or finding the next large prime is currently a computationally expensive task at best. Here is a partial list of primality tests. In particular see AKS. –  J. W. Perry Dec 14 '13 at 21:15

1 Answer 1

up vote 1 down vote accepted

I am not sure what are you asking for but there is a famous and very simple algorithm called the Sieve of Eratosthenes that gives you all the existing primes to a certain $n\in \Bbb N$.

There is also a theorem that says: "If $n$ is a composed integer, then it has a prime factor that does not exceed $\sqrt{n}$". So, for example, if we want to verify if $103$ is prime we would search for the primes that do not exceed $\sqrt{103}$ wich are $2,3,4,5,7$. Then we would verify if they are factors of $103$. Because they are not, then there is no prime factor that exceeds $\sqrt{103}$, thus $103$ is not a composed integer, meaning that is a prime number.

share
    
My question was not precise due to my lack of knowledge on the algorithms, and "best" is relative. In my search I found so many algorithms to calculate the primes that I was kind of lost and all of them seemed to envolve some kind of testing. But now have all the answers I wanted: I know, according to Euclid's theorem, that there are infinitely many prime numbers (against my intuition). Among the methods I liked in special Sieve of Eratosthenes which is very simple and gives all the primes for a chosen n (of Naturals). –  Claudia Dec 15 '13 at 0:49

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