générateur en Python générer des nombres premiers

J'ai besoin de générer des nombres premiers en utilisant le générateur en Python. Voici mon code:

def genPrimes():
    yield 2
    x=2
    while True:
        x+=1
        for p in genPrimes():
            if (x%p)==0:
                break
        else:
            yield x

J'ai un RuntimeError: le maximum de la profondeur de récursion dépassé après la 2ème prime.next() quand je le lance.

Quel est exactement votre raison de vouloir utiliser la récursivité ici?
stackoverflow.com/questions/1628949/...
Voir le plus Rapide moyen de la liste de tous les nombres premiers en dessous de N en python
Voir ceci réponse efficace pour une premier générateur.
ou de ses amélioré, plus efficace variante.

OriginalL'auteur user1347096 | 2013-03-29

  1. 8

    Le moyen le plus rapide pour générer des nombres premiers est avec un tamis. Ici, nous utilisons une segmentation Crible d'Eratosthène pour générer les nombres premiers, un par un, sans maximum, dans l'ordre; ps est la liste de tamisage nombres premiers inférieur au courant maximal et qs est le décalage du plus petit multiple de l'correspondant ps dans le segment en cours.

    def genPrimes():
def isPrime(n):
if n % 2 == 0: return n == 2
d = 3
while d * d <= n:
if n % d == 0: return False
d += 2
return True
def init(): # change to Sieve of Eratosthenes
ps, qs, sieve = [], [], [True] * 50000
p, m = 3, 0
while p * p <= 100000:
if isPrime(p):
ps.insert(0, p)
qs.insert(0, p + (p-1) / 2)
m += 1
p += 2
for i in xrange(m):
for j in xrange(qs[i], 50000, ps[i]):
sieve[j] = False
return m, ps, qs, sieve
def advance(m, ps, qs, sieve, bottom):
for i in xrange(50000): sieve[i] = True
for i in xrange(m):
qs[i] = (qs[i] - 50000) % ps[i]
p = ps[0] + 2
while p * p <= bottom + 100000:
if isPrime(p):
ps.insert(0, p)
qs.insert(0, (p*p - bottom - 1)/2)
m += 1
p += 2
for i in xrange(m):
for j in xrange(qs[i], 50000, ps[i]):
sieve[j] = False
return m, ps, qs, sieve
m, ps, qs, sieve = init()
bottom, i = 0, 1
yield 2
while True:
if i == 50000:
bottom = bottom + 100000
m, ps, qs, sieve = advance(m, ps, qs, sieve, bottom)
i = 0
elif sieve[i]:
yield bottom + i + i + 1
i += 1
else: i += 1

    Un simple isPrime à l'aide de la section de première instance est suffisante car elle sera limitée à la quatrième racine de n. La taille du segment 2 * delta est arbitrairement fixée à 100000. Cette méthode nécessite O(sqrt n) de l'espace pour le tamisage de nombres premiers plus constante de l'espace pour le tamis.

    Il est plus lent mais permet d'économiser de l'espace pour générer candidat nombres premiers avec une roue et de tester les candidats pour la primalité avec un isPrime sur la base forte pseudoprime tests pour les bases 2, 7 et 61; ceci est valable pour 2^32.

    def genPrimes(): # valid to 2^32
def isPrime(n):
def isSpsp(n, a):
d, s = n-1, 0
while d % 2 == 0:
d /= 2; s += 1
t = pow(a,d,n)
if t == 1: return True
while s > 0:
if t == n-1: return True
t = (t*t) % n; s -= 1
return False
for p in [2, 7, 61]:
if n % p == 0: return n == p
if not isSpsp(n, p): return False
return True
w, wheel = 0, [1,2,2,4,2,4,2,4,6,2,6,4,2,4,\
6,6,2,6,4,2,6,4,6,8,4,2,4,2,4,8,6,4,6,\
2,4,6,2,6,6,4,2,4,6,2,6,4,2,4,2,10,2,10]
p = 2; yield p
while True:
p = p + wheel[w]
w = 4 if w == 51 else w + 1
if isPrime(p): yield p

    Si vous êtes intéressé par la programmation par les nombres premiers, j'ai modestement recommander cet essai à mon blog.

    quelles sont les autres listes de bases pour isSpsp et leurs plages de validité? Où peut-on trouver? Merci.
    href="http://miller-rabin.appspot.com/" >miller-rabin.appspot.com
    La "meilleure solution", est le plus petit nombre que les imbéciles le test. Par exemple, étant donné les trois premier set 2, 7, 61, le plus petit nombre composé que les rapports de test en tant que premier est 4759123141. Ou bien c'est le plus grand nombre qui ne veut pas tromper le test. J'ai oublié laquelle, mais il serait facile pour vous de vérifier. Charles Greathouse et Jeff Gilchrist ont aussi travaillé dans ce domaine, si vous voulez google pour leurs sites web, mais si vous voulez juste la réponse, la page est le plus simple endroit pour chercher.
    merci! aussi trouvé le simple liste pour les "petits" nombres dans la page WP liés à partir de cette page, vous avez mentionné. 🙂

    OriginalL'auteur user448810

  2. 7

    genPrimes() sans condition s'appelle elle-même avec exactement les mêmes arguments. Cela conduit à une récursion infinie.

    Ici est une façon de le faire à l'aide d'un (non récursif) générateur:

    def gen_primes():
n = 2
primes = set()
while True:
for p in primes:
if n % p == 0:
break
else:
primes.add(n)
yield n
n += 1

    Noter que c'est optimisé pour des raisons de simplicité et de clarté plutôt que sur la performance.

    je vous remercie. ce que ferait nombres premiers=gen_primes() comparer les nombres premiers=set()?
    est set garanti pour produire son contenu à la for énumération dans l'ordre de leur ajout dans le jeu?
    Je ne pense pas que c'est, mais je ne vois pas en quoi le fait que les questions.
    je vous remercie. Il importe seulement de l'efficacité, mais comme vous l'avez dit, vous n'êtes pas concerné par ici, donc, ici, il n'a pas d'importance.
    sur cette version, il ne sera pas question, bien sûr que c'est un bien plus gros problème, ne pas s'arrêter à la racine carrée du nombre d'être testé. Et apparemment, il pas arrêter, comme les nombres premiers viennent dans non ordonnée. 🙂

    OriginalL'auteur NPE

  3. 2

    Un bon, moyen rapide de trouver des nombres premiers. n est la limite supérieure pour arrêter la recherche.

    def prime(i, primes):
for prime in primes:
if not (i == prime or i % prime):
return False
primes.add(i)
return i
def find_primes(n):
primes = set([2])
i, p = 2, 0
while True:
if prime(i, primes):
p += 1
if p == n:
return primes
i += 1

    OriginalL'auteur MattDMo

  4. 1

    Très sympa! Vous avez juste oublié d'arrêter de prendre les nombres premiers de l'intérieur genPrimes() lorsque la racine carrée de x est atteint. C'est tout. 

    def genPrimes():
yield 2 
x=2
while True:
x+=1
for p in genPrimes():
if p*p > x:        # 
yield x        #
break          # 
if (x%p)==0:
break
# else:
#    yield x

    Sans elle, vous faites glisser l'extrémité profonde, ou ce qui est de l'expression. Quand un serpent qui mange sa propre queue, elle doit s'arrêter au milieu. S'il atteint sa tête, il n'y a plus de serpent (ainsi, la direction de manger ici est à l'opposé, mais il s'applique encore...).

    OriginalL'auteur Will Ness

  5. 1

    Juste un peu plus concis:

    import itertools
def check_prime(n, primes):
for p in primes:
if not n % p:
return False
return True
def prime_sieve():
primes = set()
for n in itertools.count(2):
if check_prime(n, primes):
primes.add(n)
yield n

    Et vous pouvez l'utiliser comme ceci:

    g = prime_sieve()
g.next()
=> 2
g.next()
=> 3
g.next()
=> 5
g.next()
=> 7
g.next()
=> 11

    OriginalL'auteur bogs

  6. 1

    Voici un rapide et claire impératif premier générateur de pas à l'aide de tamis:

    def gen_primes():
n = 2
primes = []
while True:
is_prime = True
for p in primes:
if p*p > n:
break
if n % p == 0:
is_prime = False
break
if is_prime:
primes.append(n)
yield n
n += 1

    Il est presque identique à NPE's réponse, mais comprend un test de racine qui accélère significativement la production de grands nombres premiers. Le résultat est le O(n) l'utilisation de l'espace pour la primes liste.

    OriginalL'auteur Rabih Kodeih

  7. 1

    Voici un script qui génère la liste des nombres premiers de 2 à nombre donné

    from math import sqrt
next = 2
n = int(raw_input())
y = [i for i in range(2, n+1)]
while y.index(next)+1 != len(y) and next < sqrt(n):
y = filter(lambda x: x%next !=0 or x==next, y)
next = y[y.index(next)+1]
print y

    C'est juste une autre mise en œuvre de Crible d'Eratosthène.

    OriginalL'auteur Santosh Linkha