<p>Alright, so maybe I shouldn't have shrunk this question sooo much... I have seen the post on <a href="https://stackoverflow.com/questions/622/most-efficient-code-for-the-first-10000-prime-numbers">the most efficient way to find the first 10000 primes</a>.  I'm looking for <strong>all possible ways</strong>.  The goal is to have a one stop shop for primality tests.  Any and all tests people know for finding prime numbers are welcome.</p>

<p>And so:</p>

<ul>
<li><strong>What are all the different ways of finding primes?</strong></li>
</ul>

[{'answer_id': 7275, 'author': 'akdom', 'author_id': 145, 'author_profile': 'https://Stackoverflow.com/users/145', 'pm_score': 2, 'selected': False, 'text': '<p><a href="http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes" rel="nofollow noreferrer">The Sieve of Eratosthenes</a> is a decent algorithm:</p>\n\n<blockquote>\n  <ol>\n  <li>Take the list of positive integers 2 to any given Ceiling.</li>\n  <li>Take the next item in the list (2 in the first iteration) and remove all multiples of it (beyond the first) from the list.</li>\n  <li>Repeat step two until you reach the given Ceiling.</li>\n  <li>Your list is now composed purely of primes.</li>\n  </ol>\n</blockquote>\n\n<p>There is a functional limit to this algorithm in that it exchanges speed for memory.  When generating very large lists of primes the memory capacity needed skyrockets.</p>\n'}, {'answer_id': 7281, 'author': 'akdom', 'author_id': 145, 'author_profile': 'https://Stackoverflow.com/users/145', 'pm_score': 2, 'selected': False, 'text': '<p>For a given integer, the fastest primality check I know is:</p>\n\n<blockquote>\n  <ol>\n  <li>Take a list of 2 to the square root of <strong>the integer</strong>.</li>\n  <li>Loop through the list, taking the remainder of <strong>the integer</strong> / <strong>current number</strong>\n  \n  <blockquote>\n    <ol>\n    <li>If the remainder is zero for any number in the list, then the integer is not prime.</li>\n    <li>If the remainder was non-zero for all numbers in the list, then the integer is prime.</li>\n    </ol>\n  </blockquote></li>\n  </ol>\n</blockquote>\n\n<p>It uses significantly less memory than <a href="http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes" rel="nofollow noreferrer">The Sieve of Eratosthenes</a> and is generally faster for individual numbers.</p>\n'}, {'answer_id': 7314, 'author': 'goric', 'author_id': 940, 'author_profile': 'https://Stackoverflow.com/users/940', 'pm_score': 0, 'selected': False, 'text': '<p>In your algorithm using the list from 2 to the root of the integer, you can improve performance by only testing odd numbers after 2.  That is, your list only needs to contain 2 and all odd numbers from 3 to the square root of the integer.  This cuts the number of times you loop in half without introducing any more complexity.</p>\n'}, {'answer_id': 7323, 'author': 'akdom', 'author_id': 145, 'author_profile': 'https://Stackoverflow.com/users/145', 'pm_score': 0, 'selected': False, 'text': "<p>@theprise</p>\n\n<p>If I were wanting to use an incrementing loop instead of an instantiated list (problems with memory for massive numbers...), what would be a good way to do that without building the list?</p>\n\n<p>It doesn't seem like it would be cheaper to do a divisibility check for the given integer (X % 3) than just the check for the normal number (N % X).</p>\n"}, {'answer_id': 7380, 'author': 'GateKiller', 'author_id': 383, 'author_profile': 'https://Stackoverflow.com/users/383', 'pm_score': -1, 'selected': False, 'text': '<p>If you\'re wanting to find a way of generating prime numbers, this have been covered in a <a href="https://stackoverflow.com/questions/622/most-efficient-code-for-the-first-10000-prime-numbers#2753">previous question</a>.</p>\n'}, {'answer_id': 7476, 'author': 'goric', 'author_id': 940, 'author_profile': 'https://Stackoverflow.com/users/940', 'pm_score': 2, 'selected': False, 'text': "<p>@akdom's question to me:</p>\n\n<p>Looping would work fine on my previous suggestion, and you don't need to do any calculations to determine if a number is even; in your loop, simply skip every even number, as shown below:</p>\n\n<pre><code>//Assuming theInteger is the number to be tested for primality.\n// Check if theInteger is divisible by 2.  If not, run this loop.\n//  This loop skips all even numbers.\nfor( int i = 3; i &lt; sqrt(theInteger); i + 2) \n{\n    if( theInteger % i == 0) \n    {\n       //getting here denotes that theInteger is not prime \n       // somehow indicate that some number, i, divides it and break\n       break;\n    }\n}\n</code></pre>\n"}, {'answer_id': 7487, 'author': 'nlucaroni', 'author_id': 157, 'author_profile': 'https://Stackoverflow.com/users/157', 'pm_score': 2, 'selected': False, 'text': '<p>A Rutgers grad student recently found a <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL11/Rowland/rowland21.html" rel="nofollow noreferrer">recurrence relation that generates primes</a>. The difference of its successive numbers will generate either primes or 1\'s.</p>\n\n<pre><code>a(1) = 7\na(n) = a(n-1) + gcd(n,a(n-1)). \n</code></pre>\n\n<p>It makes a lot of crap that needs to be filtered out. Benoit Cloitre also has this recurrence that does a similar task:</p>\n\n<pre><code>b(1) = 1\nb(n) = b(n-1) + lcm(n,b(n-1))\n</code></pre>\n\n<p>then the ratio of successive numbers, minus one [b(n)/b(n-1)-1] is prime. A full account of all this can be read at <a href="http://recursed.blogspot.com/2008/07/rutgers-graduate-student-finds-new.html" rel="nofollow noreferrer">Recursivity</a>.</p>\n\n<p>For the sieve, you can do better by using a wheel instead of adding one each time, check out the <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.52.835" rel="nofollow noreferrer">Improved Incremental Prime Number Sieves</a>. Here is an example of a wheel. Let\'s look at the numbers, 2 and 5 to ignore. Their wheel is, [2,4,2,2].</p>\n'}, {'answer_id': 242398, 'author': 'Artelius', 'author_id': 31945, 'author_profile': 'https://Stackoverflow.com/users/31945', 'pm_score': 2, 'selected': False, 'text': '<p>Some prime tests only work with certain numbers, for instance, the <a href="http://en.wikipedia.org/wiki/Lucas%E2%80%93Lehmer_test_for_Mersenne_numbers" rel="nofollow noreferrer">Lucas–Lehmer</a> test only works for Mersenne numbers.</p>\n\n<p>Most prime tests used for big numbers can only tell you that a certain number is "probably prime" (or, if the number fails the test, it is definitely <strong>not</strong> prime). Usually you can continue the algorithm until you have a very high probability of a number being prime.</p>\n\n<p>Have a look at <a href="http://en.wikipedia.org/wiki/Pseudoprime" rel="nofollow noreferrer">this page</a> and especially its "See Also" section.</p>\n\n<p>The <a href="http://en.wikipedia.org/wiki/Miller-Rabin_test" rel="nofollow noreferrer">Miller-Rabin test</a> is, I think, one of the best tests. In its standard form it gives you probable primes - though it has been shown that if you apply the test to a number beneath 3.4*10^14, and it passes the test for each parameter 2, 3, 5, 7, 11, 13 and 17, it is <em>definitely</em> prime.</p>\n\n<p>The <a href="http://en.wikipedia.org/wiki/AKS_primality_test" rel="nofollow noreferrer">AKS test</a> was the first deterministic, proven, general, polynomial-time test. However, to the best of my knowledge, its best implementation turns out to be slower than other tests unless the input is ridiculously large.</p>\n'}]
['https://Stackoverflow.com/questions/7272', 'https://Stackoverflow.com', 'https://Stackoverflow.com/users/145/']