Popular recipes tagged "primes"http://code.activestate.com/recipes/tags/primes/popular/2017-04-25T11:44:27-07:00ActiveState Code RecipesBatch prime generator (Batch)
2017-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>
Prime factors of an integer by Brent algorithm (Python)
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>
Public Key Encryption (RSA) (Python)
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>
de Polignac's Formula (Python)
2013-08-10T03:40:02-07:00Samuel James Ericksonhttp://code.activestate.com/recipes/users/4187478/http://code.activestate.com/recipes/578632-de-polignacs-formula/
<p style="color: grey">
Python
recipe 578632
by <a href="/recipes/users/4187478/">Samuel James Erickson</a>
(<a href="/recipes/tags/factorial/">factorial</a>, <a href="/recipes/tags/n/">n</a>, <a href="/recipes/tags/prime/">prime</a>, <a href="/recipes/tags/primes/">primes</a>).
Revision 4.
</p>
<p>Obtains the total number of factors of p in n! for any prime p.</p>
Find the nth prime in python (Python)
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>
Genreate x digits prime number in python, version 2 (Python)
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>
Public Key Encryption (RSA) (Python)
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>
Evolutionary Algorithm (Generation of Prime Numbers) (Python)
2011-11-27T06:45:00-08:00Alexander James Wallarhttp://code.activestate.com/recipes/users/4179768/http://code.activestate.com/recipes/577964-evolutionary-algorithm-generation-of-prime-numbers/
<p style="color: grey">
Python
recipe 577964
by <a href="/recipes/users/4179768/">Alexander James Wallar</a>
(<a href="/recipes/tags/algorithm/">algorithm</a>, <a href="/recipes/tags/example/">example</a>, <a href="/recipes/tags/genetic/">genetic</a>, <a href="/recipes/tags/genetic_algorithm/">genetic_algorithm</a>, <a href="/recipes/tags/genetic_algorithms/">genetic_algorithms</a>, <a href="/recipes/tags/list/">list</a>, <a href="/recipes/tags/number/">number</a>, <a href="/recipes/tags/of/">of</a>, <a href="/recipes/tags/prime/">prime</a>, <a href="/recipes/tags/primelist/">primelist</a>, <a href="/recipes/tags/primes/">primes</a>, <a href="/recipes/tags/theory/">theory</a>).
</p>
<p>This is an evolutionary algorithm that returns a random list of prime numbers. This code is highly inefficient for a reason. This algorithm is more of a proof of concept that if a prime was a heritable trait, it would not be a desired one. </p>
<p>Parameters:</p>
<p>isPrime --> n: number to check if it is prime
allPrimes --> n: size of list of random primes, m: the primes in the list will be between 0 and m</p>
Even faster prime generator (C++)
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>
primeList (Python)
2011-11-05T23:42:37-07:00Alexander James Wallarhttp://code.activestate.com/recipes/users/4179768/http://code.activestate.com/recipes/577935-primelist/
<p style="color: grey">
Python
recipe 577935
by <a href="/recipes/users/4179768/">Alexander James Wallar</a>
(<a href="/recipes/tags/list/">list</a>, <a href="/recipes/tags/numbers/">numbers</a>, <a href="/recipes/tags/prime/">prime</a>, <a href="/recipes/tags/primelist/">primelist</a>, <a href="/recipes/tags/primes/">primes</a>, <a href="/recipes/tags/theory/">theory</a>).
Revision 3.
</p>
<p>This module returns all the prime numbers strictly less than n. For this code to print out all of the primes n inclusive, in the range, n+1 must be substituted for n.</p>
Faster prime generator (C++)
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>
Fastest way to list all primes below N in python (Python)
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>
A fast & memory-wise prime number generator up to N (Python)
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 & 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>
Infinite list of primes! Yay! (Python)
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>
Some prime generation algorithms. (Python)
2010-08-06T11:20:34-07:00Thomas Lehmannhttp://code.activestate.com/recipes/users/4174477/http://code.activestate.com/recipes/577329-some-prime-generation-algorithms/
<p style="color: grey">
Python
recipe 577329
by <a href="/recipes/users/4174477/">Thomas Lehmann</a>
(<a href="/recipes/tags/generation/">generation</a>, <a href="/recipes/tags/is_prime/">is_prime</a>, <a href="/recipes/tags/prime/">prime</a>, <a href="/recipes/tags/primes/">primes</a>).
Revision 4.
</p>
<p>Basic idea was to see the difference between different prime algorithms in time. Also they are not perfect the output shows that really higher numbers let grow the difference why I have separated this into functions to make it visible. I add this here because I have been missing this very often when I have been searching for algorithms.</p>
<ul>
<li>The 'is_prime' is a well known way of checkin for a number being prime or not.</li>
<li>The sieve of Erastothenes is simply to strike out multiples of a given value; the primes will remain.</li>
<li>the function 'profile' is a decorator for functions measuring the execution time</li>
<li>Some information are in the comments of the code</li>
</ul>
Find 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>
Prime, Perfect and Fibonacci Number Widget Class (Python)
2010-05-19T17:02:28-07:00AJ. Mayorgahttp://code.activestate.com/recipes/users/4173476/http://code.activestate.com/recipes/577229-prime-perfect-and-fibonacci-number-widget-class/
<p style="color: grey">
Python
recipe 577229
by <a href="/recipes/users/4173476/">AJ. Mayorga</a>
(<a href="/recipes/tags/cryptography/">cryptography</a>, <a href="/recipes/tags/numbers/">numbers</a>, <a href="/recipes/tags/prime/">prime</a>, <a href="/recipes/tags/primes/">primes</a>).
Revision 2.
</p>
<p>A class Ive had in my snippets for awhile that can generate prime, perfect and fibonacci sequences as well as check whether or not a supplied value is any of them.</p>
Simple primes generator (Python)
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>
Sieve of Eratosthenes (Python)
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 < n.</p>
Fast prime generator (C++)
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>