Simple Prime Generator en Python

def is_prime(num):
    """Returns True if the number is prime
    else False."""
    if num == 0 or num == 1:
        return False
    for x in range(2, num):
        if num % x == 0:
            return False
    else:
        return True

>> filter(is_prime, range(1, 20))
  [2, 3, 5, 7, 11, 13, 17, 19]

Nous allons obtenir tous les nombres premiers jusqu'à 20 dans une liste. J'aurais pu utiliser un tamis D'Eratosthène mais vous avez dit vous voulez quelque chose de très simple. ;)

print [x for x in range(2,100) if not [t for t in range(2,x) if not x%t]]

re est puissant:

import re


def isprime(n):
    return re.compile(r'^1?$|^(11+)+$').match('1' * n) is None

print [x for x in range(100) if isprime(x)]

###########Output#############
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

def primes(n): # simple Sieve of Eratosthenes 
   odds = range(3, n+1, 2)
   sieve = set(sum([range(q*q, n+1, q+q) for q in odds],[]))
   return [2] + [p for p in odds if p not in sieve]

>>> primes(50)
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

Pour tester si un nombre est premier:

>>> 541 in primes(541)
True
>>> 543 in primes(543)
False

Voici un simple (Python 2.6.2) solution... ce qui est conforme à la demande initiale de L'OP (qui date maintenant de six mois); et devrait être une solution parfaitement acceptable dans tout cours de "programmation 101"... D'où ce post.

import math

def isPrime(n):
    for i in range(2, int(math.sqrt(n)+1)):
        if n % i == 0: 
            return False;
    return n>1;

print 2
for n in range(3, 50):
    if isPrime(n):
        print n

cette méthode simple "brute force" est "assez rapide" pour les nombres jusqu'à environ 16.000 sur PC moderne (a pris environ 8 secondes sur ma boîte de 2GHz).

évidemment, cela pourrait être fait beaucoup plus efficacement, en ne recalculant pas le primeness de chaque nombre pair, ou tout multiple de 3, 5, 7, etc pour chaque numéro unique... Voir le tamis D'Eratosthènes (voir la mise en œuvre d'eliben ci-dessus), ou même le tamis D'Atkin si vous vous sentez particulièrement courageux et/ou fou.

Caveat Emptor: je suis un python de noob. Ne prenez rien de ce que je dis comme Évangile.

donc je crée d'abord une fonction pour savoir si le nombre est Premier ou ne pas l'utiliser en boucle ou à un autre endroit si nécessaire.

def isprime(n):
      for x in range(2,n):
        if n%x == 0:
            return False
    return True

puis lancez une simple expression de compréhension de liste ou de générateur pour obtenir votre liste de prime,

[x for x in range(1,100) if isprime(x)]

Cela semble devoirs-y, donc, je vais donner un indice plutôt qu'une explication détaillée. Corrigez-moi si j'ai supposé mal.

Vous faites bien comme renflouer quand vous voyez un même diviseur.

mais vous imprimez 'count' dès que vous voyez même nombre qui ne divise pas. 2, par exemple, ne se divise pas également en 9. Mais ça ne fait pas de 9 un prime. Vous pourriez vouloir continuer à aller jusqu'à ce que vous êtes sûr aucun dans la plage de matchs.

(comme d'autres ont répondu, le Tamis est une façon beaucoup plus efficace d'aller... juste essayer de vous aider à comprendre pourquoi ce code n'est pas de faire ce que vous voulez)

Que Diriez-vous de ceci si vous voulez calculer la prime directement:

def oprime(n):
counter = 0
b = 1
if n == 1:
    print 2
while counter < n-1:
    b = b + 2
    for a in range(2,b):
        if b % a == 0:
            break
    else:
        counter = counter + 1
        if counter == n-1:
            print b

un autre exemple simple, avec une optimisation simple de ne considérer que les nombres impairs. Tout est fait avec des flux paresseux (générateurs python).

Utilisation: amorce = liste(create_prime_iterator(1, 30))

import math
import itertools

def create_prime_iterator(rfrom, rto):
    """Create iterator of prime numbers in range [rfrom, rto]"""
    prefix = [2] if rfrom < 3 and rto > 1 else [] # include 2 if it is in range separately as it is a "weird" case of even prime
    odd_rfrom = 3 if rfrom < 3 else make_odd(rfrom) # make rfrom an odd number so that  we can skip all even nubers when searching for primes, also skip 1 as a non prime odd number.
    odd_numbers = (num for num in xrange(odd_rfrom, rto + 1, 2))
    prime_generator = (num for num in odd_numbers if not has_odd_divisor(num))
    return itertools.chain(prefix, prime_generator)

def has_odd_divisor(num):
    """Test whether number is evenly divisable by odd divisor."""
    maxDivisor = int(math.sqrt(num))
    for divisor in xrange(3, maxDivisor + 1, 2):
        if num % divisor == 0:
            return True
    return False

def make_odd(number):
    """Make number odd by adding one to it if it was even, otherwise return it unchanged"""
    return number | 1

• la déclaration continue semble fausse.

• Vous souhaitez démarrer à 2 car 2 est le premier nombre premier.

• Vous pouvez écrire "while True:" pour obtenir une boucle infinie.

vous devez vous assurer que tous les diviseurs possibles ne divisent pas également le nombre que vous vérifiez. Dans ce cas, vous imprimerez le nombre que vous vérifiez à tout moment juste un des diviseurs possibles ne divise pas également le nombre.

vous ne voulez pas non plus utiliser une instruction continuer parce qu'une suite la causera juste pour vérifier le diviseur suivant possible quand vous avez déjà découvert que le nombre n'est pas un premier.

Voici ce que j'ai:

def is_prime(num):
    if num < 2:         return False
    elif num < 4:       return True
    elif not num % 2:   return False
    elif num < 9:       return True
    elif not num % 3:   return False
    else:
        for n in range(5, int(math.sqrt(num) + 1), 6):
            if not num % n:
                return False
            elif not num % (n + 2):
                return False

    return True

c'est assez rapide pour les grands nombres, car il vérifie seulement contre les nombres déjà premiers pour les diviseurs d'un nombre.

Maintenant, si vous voulez générer une liste de nombres premiers, vous pouvez faire:

# primes up to 'max'
def primes_max(max):
    yield 2
    for n in range(3, max, 2):
        if is_prime(n):
            yield n

# the first 'count' primes
def primes_count(count):
    counter = 0
    num = 3

    yield 2

    while counter < count:
        if is_prime(num):
            yield num
            counter += 1
        num += 2

l'utilisation de générateurs ici pourrait être souhaitable pour l'efficacité.

Et juste pour la référence, au lieu de dire:

one = 1
while one == 1:
    # do stuff

vous pouvez simplement dire:

while 1:
    #do stuff

Vous pouvez créer une liste de nombres premiers en utilisant des compréhensions de liste d'une manière assez élégante. Prises de ici:

>>> noprimes = [j for i in range(2, 8) for j in range(i*2, 50, i)]
>>> primes = [x for x in range(2, 50) if x not in noprimes]
>>> print primes
>>> [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

def genPrimes():
    primes = []   # primes generated so far
    last = 1      # last number tried
    while True:
        last += 1
        for p in primes:
            if last % p == 0:
                break
        else:
            primes.append(last)
            yield last

similaire à user107745, mais en utilisant ' all ' au lieu de la double négation (un peu plus lisible, mais je pense que la même performance):

import math
[x for x in xrange(2,10000) if all(x%t for t in xrange(2,int(math.sqrt(x))+1))]

fondamentalement, il itère sur x dans la gamme de (2, 100) et ne sélectionne que ceux qui n'ont pas mod == 0 pour tout t dans la gamme(2,x)

une Autre façon est probablement juste de peupler le premier des nombres, comme nous allons:

primes = set()
def isPrime(x):
  if x in primes:
    return x
  for i in primes:
    if not x % i:
      return None
  else:
    primes.add(x)
    return x

filter(isPrime, range(2,10000))

def check_prime(x):
    if (x < 2): 
       return 0
    elif (x == 2): 
       return 1
    t = range(x)
    for i in t[2:]:
       if (x % i == 0):
            return 0
    return 1

SymPy est une bibliothèque Python pour les mathématiques symboliques. Il offre plusieurs fonctions pour générer des nombres premiers.

isprime(n)              # Test if n is a prime number (True) or not (False).

primerange(a, b)        # Generate a list of all prime numbers in the range [a, b).
randprime(a, b)         # Return a random prime number in the range [a, b).
primepi(n)              # Return the number of prime numbers less than or equal to n.

prime(nth)              # Return the nth prime, with the primes indexed as prime(1) = 2. The nth prime is approximately n*log(n) and can never be larger than 2**n.
prevprime(n, ith=1)     # Return the largest prime smaller than n
nextprime(n)            # Return the ith prime greater than n

sieve.primerange(a, b)  # Generate all prime numbers in the range [a, b), implemented as a dynamically growing sieve of Eratosthenes. 

Ici sont quelques exemples.

>>> import sympy
>>> 
>>> sympy.isprime(5)
True
>>> list(sympy.primerange(0, 100))
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
>>> sympy.randprime(0, 100)
83
>>> sympy.randprime(0, 100)
41
>>> sympy.prime(3)
5
>>> sympy.prevprime(50)
47
>>> sympy.nextprime(50)
53
>>> list(sympy.sieve.primerange(0, 100))
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

si vous voulez trouver tous les nombres premiers dans une plage, vous pouvez faire ceci:

def is_prime(num):
"""Returns True if the number is prime
else False."""
if num == 0 or num == 1:
    return False
for x in range(2, num):
    if num % x == 0:
        return False
else:
    return True
num = 0
itr = 0
tot = ''
while itr <= 100:
    itr = itr + 1
    num = num + 1
    if is_prime(num) == True:
        print(num)
        tot = tot + ' ' + str(num)
print(tot)

il suffit d'ajouter while its <= et votre numéro pour la gamme.

OUTPUT:

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101

Voici une version compacte du tamis D'Eratosthènes ayant à la fois une complexité acceptable (plus faible que le tri d'un tableau de longueur n) et une vectorisation.

import numpy as np 
def generate_primes(n):
    is_prime = np.ones(n+1,dtype=bool)
    is_prime[0:2] = False
    for i in range(int(n**0.5)+1):
        if is_prime[i]:
            is_prime[i*2::i]=False
    return np.where(is_prime)[0]

Horaires:

import time    
for i in range(2,10):
    timer =time.time()
    generate_primes(10**i)
    print('n = 10^',i,' time =', round(time.time()-timer,6))

>> n = 10^ 2  time = 5.6e-05
>> n = 10^ 3  time = 6.4e-05
>> n = 10^ 4  time = 0.000114
>> n = 10^ 5  time = 0.000593
>> n = 10^ 6  time = 0.00467
>> n = 10^ 7  time = 0.177758
>> n = 10^ 8  time = 1.701312
>> n = 10^ 9  time = 19.322478

import time

maxnum=input("You want the prime number of 1 through....")

n=2
prime=[]
start=time.time()

while n<=maxnum:

    d=2.0
    pr=True
    cntr=0

    while d<n**.5:

        if n%d==0:
            pr=False
        else:
            break
        d=d+1

    if cntr==0:

        prime.append(n)
        #print n

    n=n+1

print "Total time:",time.time()-start

pour moi, la solution ci-dessous semble simple et facile à suivre.

import math

def is_prime(num):

    if num < 2:
        return False

    for i in range(2, int(math.sqrt(num) + 1)):
        if num % i == 0:
            return False

return True