Popular recipes tagged "primality_testing" and "prime_generator"http://code.activestate.com/recipes/tags/primality_testing+prime_generator/2010-06-12T08:22:40-07:00ActiveState Code RecipesFind Prime Numbers in python (Python)
2010-06-12T08:22:40-07:00Giannis Fysakishttp://code.activestate.com/recipes/users/4174072/http://code.activestate.com/recipes/577259-find-prime-numbers-in-python/
<p style="color: grey">
Python
recipe 577259
by <a href="/recipes/users/4174072/">Giannis Fysakis</a>
(<a href="/recipes/tags/algorithm/">algorithm</a>, <a href="/recipes/tags/algorithms/">algorithms</a>, <a href="/recipes/tags/primality_testing/">primality_testing</a>, <a href="/recipes/tags/prime/">prime</a>, <a href="/recipes/tags/primes/">primes</a>, <a href="/recipes/tags/prime_generator/">prime_generator</a>, <a href="/recipes/tags/prime_number/">prime_number</a>).
Revision 2.
</p>
<p>The algorithm is based on the idea <br />
that the next larger prime after one prime is the sum of the two smaller previous minus three prime numbers back.
For the first five prime numbers 2,3,5,7,11 this pattern is not true also it is not true if the number is a composite number (including of course if the number's square root is integer). </p>
<p>Example
trying to find the tenth prime</p>
<p>so lets play with numbers 17(minus 3 from Next,position 7), 19(minus 2 from Next,position 8), 23(minus 1 from Next,position 9) and number Next at position 10 :</p>
<p>hmmm ... if we add 19 and 23 we get 42, but 42 minus 17 equals 25 which isn't a prime :(</p>
<p>In order to correct this we assume that 25 is the next prime number ( temporary holding the tenth position)
finally to get the real Next prime number we take 23 + 25 = 48 , we subtract 19 and we get 29 which finally it takes the tenth position ( because it deserves it :P)</p>