Top-rated recipes tagged "prime" Code RecipesInverse modulo p (Python) 2013-01-31T23:41:21-08:00Justin Shaw <p style="color: grey"> Python recipe 576737 by <a href="/recipes/users/1523109/">Justin Shaw</a> (<a href="/recipes/tags/mod/">mod</a>, <a href="/recipes/tags/modulo/">modulo</a>, <a href="/recipes/tags/number/">number</a>, <a href="/recipes/tags/prime/">prime</a>, <a href="/recipes/tags/theory/">theory</a>). Revision 4. </p> <p>Very rarely it is necessary to find the multiplicative inverse of a number in the ring of integers modulo p. Thie recipe handles those rare cases. That is, given x, an integer, and p the modulus, we seek a integer x^-1 such that x * x^-1 = 1 mod p. For example 38 is the inverse of 8 modulo 101 since 38 * 8 = 304 = 1 mod 101. The inverse only exists when a and p are relatively prime.</p> primeList (Python) 2011-11-05T23:42:37-07:00Alexander James Wallar <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> de Polignac's Formula (Python) 2013-08-10T03:40:02-07:00Samuel James Erickson <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> Evolutionary Algorithm (Generation of Prime Numbers) (Python) 2011-11-27T06:45:00-08:00Alexander James Wallar <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> Some prime generation algorithms. (Python) 2010-08-06T11:20:34-07:00Thomas Lehmann <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 Fysakis <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. Mayorga <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> Primes from 1 to 100 (Python) 2009-11-13T09:47:53-08:00Adam M Prost <p style="color: grey"> Python recipe 576956 by <a href="/recipes/users/4172124/">Adam M Prost</a> (<a href="/recipes/tags/prime/">prime</a>). Revision 2. </p> <p>Get the primes from 1 to 100 or really any range you choose.</p> Prime Number Generator (Python) 2009-02-03T15:47:06-08:00dth <p style="color: grey"> Python recipe 576640 by <a href="/recipes/users/4169078/">dth</a> (<a href="/recipes/tags/eratosthene/">eratosthene</a>, <a href="/recipes/tags/generator/">generator</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/sieve/">sieve</a>). Revision 7. </p> <p>Generate all prime numbers up to n.</p>