http://code.activestate.com/recipes/tags/primes-prime/2017-04-25T11:44:27-07:00ActiveState Code Recipes2017-04-25T11:44:27-07:00Antoni Gualhttp://code.activestate.com/recipes/users/4182514/http://code.activestate.com/recipes/580789-batch-prime-generator/

<p style="color: grey"> Batch recipe 580789 by <a href="/recipes/users/4182514/">Antoni Gual</a> (<a href="/recipes/tags/primes/">primes</a>). Revision 3. </p> <p>Here is a radically differnt approach to generating primes in pure batch that overperforms everything else I have found . The idea comes from an exercise in Knuth's TAOCP Vol 3 page 617.</p>

2015-05-28T06:47:01-07:00Antoni Gualhttp://code.activestate.com/recipes/users/4182514/http://code.activestate.com/recipes/579049-prime-factors-of-an-integer-by-brent-algorithm/

<p style="color: grey"> Python recipe 579049 by <a href="/recipes/users/4182514/">Antoni Gual</a> (<a href="/recipes/tags/primes/">primes</a>, <a href="/recipes/tags/python/">python</a>). </p> <p>This recipe uses trial division to get factors below 1 milion then switches to Brent's algorithm to get bigger factors. No fast enough to break a RSA key :)</p>

2013-12-27T06:43:59-08:00Mohammad Taha Jahangirhttp://code.activestate.com/recipes/users/4188847/http://code.activestate.com/recipes/578797-public-key-encryption-rsa/

<p style="color: grey"> Python recipe 578797 by <a href="/recipes/users/4188847/">Mohammad Taha Jahangir</a> (<a href="/recipes/tags/encryption/">encryption</a>, <a href="/recipes/tags/inverse/">inverse</a>, <a href="/recipes/tags/multiplicative/">multiplicative</a>, <a href="/recipes/tags/primality_testing/">primality_testing</a>, <a href="/recipes/tags/primes/">primes</a>, <a href="/recipes/tags/publickey/">publickey</a>, <a href="/recipes/tags/rsa/">rsa</a>). Revision 3. </p> <p>Simple code to create and use public/private keypairs. Accompanied by a rudimentary encoder.</p>

2013-01-06T20:23:21-08:00Captain DeadBoneshttp://code.activestate.com/recipes/users/4184772/http://code.activestate.com/recipes/578403-find-the-nth-prime-in-python/

<p style="color: grey"> Python recipe 578403 by <a href="/recipes/users/4184772/">Captain DeadBones</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>). </p> <p>This is a nth prime number generator in python that I put together for an article I wrote <a href="http://thelivingpearl.com/2013/01/06/how-to-find-prime-numbers-in-python/">How To Find Prime Numbers In Python</a></p>

2013-01-06T20:27:09-08:00Captain DeadBoneshttp://code.activestate.com/recipes/users/4184772/http://code.activestate.com/recipes/578405-genreate-x-digits-prime-number-in-python-version-2/

<p style="color: grey"> Python recipe 578405 by <a href="/recipes/users/4184772/">Captain DeadBones</a> (<a href="/recipes/tags/primes/">primes</a>, <a href="/recipes/tags/prime_generator/">prime_generator</a>). </p> <p>This is a prime number generator in python that I put together for an article I wrote <a href="http://thelivingpearl.com/2013/01/06/how-to-find-prime-numbers-in-python/">How To Find Prime Numbers In Python</a>. The script will generate a prime number of x digits, where x is less than 15. It might work for larger x, but it will take a while. </p>

2012-05-12T23:34:22-07:00Raymond Hettingerhttp://code.activestate.com/recipes/users/178123/http://code.activestate.com/recipes/577737-public-key-encryption-rsa/

<p style="color: grey"> Python recipe 577737 by <a href="/recipes/users/178123/">Raymond Hettinger</a> (<a href="/recipes/tags/encryption/">encryption</a>, <a href="/recipes/tags/inverse/">inverse</a>, <a href="/recipes/tags/multiplicative/">multiplicative</a>, <a href="/recipes/tags/primality_testing/">primality_testing</a>, <a href="/recipes/tags/primes/">primes</a>, <a href="/recipes/tags/publickey/">publickey</a>, <a href="/recipes/tags/rsa/">rsa</a>). Revision 2. </p> <p>Simple code to create and use public/private keypairs. Accompanied by a rudimentary encoder.</p>

2011-11-27T21:48:25-08:00Sumudu Fernandohttp://code.activestate.com/recipes/users/4180103/http://code.activestate.com/recipes/577966-even-faster-prime-generator/

<p style="color: grey"> C++ recipe 577966 by <a href="/recipes/users/4180103/">Sumudu Fernando</a> (<a href="/recipes/tags/primes/">primes</a>, <a href="/recipes/tags/prime_generator/">prime_generator</a>). </p> <p>A very quick (segmented) sieve of Eratosthenes.</p> <p>Takes ~6s on a midrange machine to hit all 50 847 534 primes less than 1 billion, ending with 999999937</p> <p>If you want to actually <em>do</em> anything with every prime (beyond counting them), there are three places to add a statement doing whatever is necessary with "lastP" -- one at the top (handles the special case '2'), one in the middle (handles "small" primes which are actually used to sieve), and one at the bottom (handles "large" primes which merely survive sieving).</p> <p>In principle one can use a function object as parameter to allow generic operations on the primes, so add that if you want more general-purpose code (perhaps I'll do that later)</p> <p>For higher limits you need to switch to wider types and follow the commented guidelines for the constants. For a fixed limit, changing <code>B_SIZE</code> may affect performance so if needed tune it (profile as you go, of course!). But this will get quite slow if you go to much higher numbers.</p>

2011-10-08T23:26:24-07:00Mathijs Romanshttp://code.activestate.com/recipes/users/4179530/http://code.activestate.com/recipes/577899-faster-prime-generator/

<p style="color: grey"> C++ recipe 577899 by <a href="/recipes/users/4179530/">Mathijs Romans</a> (<a href="/recipes/tags/primes/">primes</a>, <a href="/recipes/tags/prime_generator/">prime_generator</a>). </p> <p>The sieve of Eratosthenes implemented in C++. I noticed <a href="http://code.activestate.com/recipes/576559-fast-prime-generator/">another recipe</a> that could be improved upon, making it faster and a bit prettier.</p>

2010-07-27T01:57:20-07:00robert.william.hankshttp://code.activestate.com/recipes/users/4174481/http://code.activestate.com/recipes/577331-fastest-way-to-list-all-primes-below-n-in-python/

<p style="color: grey"> Python recipe 577331 by <a href="/recipes/users/4174481/">robert.william.hanks</a> (<a href="/recipes/tags/fast/">fast</a>, <a href="/recipes/tags/fastest/">fastest</a>, <a href="/recipes/tags/math/">math</a>, <a href="/recipes/tags/numbers/">numbers</a>, <a href="/recipes/tags/numpy/">numpy</a>, <a href="/recipes/tags/primes/">primes</a>, <a href="/recipes/tags/python/">python</a>). Revision 6. </p> <p>I was looking for a fast way to list all primes below n, so far i came up to this with the numpy solution the fastest. It does primes up to 10e6 in 15ms in my old machine, and it is capable of reaching 10e9. </p>

2010-08-13T18:28:00-07:00robert.william.hankshttp://code.activestate.com/recipes/users/4174481/http://code.activestate.com/recipes/577357-a-fast-memory-wise-prime-number-generator-up-to-n/

<p style="color: grey"> Python recipe 577357 by <a href="/recipes/users/4174481/">robert.william.hanks</a> (<a href="/recipes/tags/fast/">fast</a>, <a href="/recipes/tags/numpy/">numpy</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>, <a href="/recipes/tags/python/">python</a>). </p> <p>Using python 2.6 &amp; numpy. This code was first posted <a href="http://stackoverflow.com/questions/2897297/speed-up-bitstring-bit-operations-in-python/2908512#2908512">here</a></p>

2010-07-20T04:05:00-07:00Alejandro Peraltahttp://code.activestate.com/recipes/users/4174433/http://code.activestate.com/recipes/577318-infinite-list-of-primes-yay/

<p style="color: grey"> Python recipe 577318 by <a href="/recipes/users/4174433/">Alejandro Peralta</a> (<a href="/recipes/tags/iterators/">iterators</a>, <a href="/recipes/tags/numbers/">numbers</a>, <a href="/recipes/tags/primes/">primes</a>). </p> <p>It's an iterator that returns prime numbers. </p> <p>Got the idea from here: <a href="http://www.cs.hmc.edu/%7Eoneill/papers/Sieve-JFP.pdf" rel="nofollow">www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf</a></p>

2009-11-04T06:52:06-08:00Maxime Fontenierhttp://code.activestate.com/recipes/users/4172150/http://code.activestate.com/recipes/576948-simple-primes-generator/

<p style="color: grey"> Python recipe 576948 by <a href="/recipes/users/4172150/">Maxime Fontenier</a> (<a href="/recipes/tags/any/">any</a>, <a href="/recipes/tags/generator/">generator</a>, <a href="/recipes/tags/numbers/">numbers</a>, <a href="/recipes/tags/primes/">primes</a>). </p> <p>Simple prime generator. </p> <p>I write it as a sample usage of the any function.</p>

2008-12-27T11:45:09-08:00Louis RIVIEREhttp://code.activestate.com/recipes/users/4035877/http://code.activestate.com/recipes/576596-sieve-of-eratosthenes/

<p style="color: grey"> Python recipe 576596 by <a href="/recipes/users/4035877/">Louis RIVIERE</a> (<a href="/recipes/tags/algorithms/">algorithms</a>, <a href="/recipes/tags/eratosthenes/">eratosthenes</a>, <a href="/recipes/tags/math/">math</a>, <a href="/recipes/tags/primes/">primes</a>). Revision 3. </p> <p>Returns primes &lt; n.</p>

2008-11-30T00:40:23-08:00Florian Mayerhttp://code.activestate.com/recipes/users/4165843/http://code.activestate.com/recipes/576559-fast-prime-generator/

<p style="color: grey"> C++ recipe 576559 by <a href="/recipes/users/4165843/">Florian Mayer</a> (<a href="/recipes/tags/primes/">primes</a>, <a href="/recipes/tags/prime_generator/">prime_generator</a>). Revision 2. </p> <p>This is the sieve of Eratosthenes implemented in C++.</p>

2008-07-26T19:45:12-07:00Phil Huffmanhttp://code.activestate.com/recipes/users/4165783/http://code.activestate.com/recipes/576380-prime-look-up-program/

<p style="color: grey"> Python recipe 576380 by <a href="/recipes/users/4165783/">Phil Huffman</a> (<a href="/recipes/tags/algorithm/">algorithm</a>, <a href="/recipes/tags/primes/">primes</a>). </p> <p>Finds the nth prime without using a sieve algorithm. </p>