Simple Premier Générateur en Python
https://stackoverflow.com/questions/567222
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Quelqu'un pourrait-il s'il vous plaît me dire ce que je fais mal avec ce code? Il est tout simplement l'impression « count » de toute façon. Je veux juste un générateur premier très simple (rien de fantaisie).
import math
def main():
count = 3
one = 1
while one == 1:
for x in range(2, int(math.sqrt(count) + 1)):
if count % x == 0:
continue
if count % x != 0:
print count
count += 1
La solution
Il y a quelques problèmes:
- Pourquoi avez-vous imprimer le nombre quand il n'a pas divisé par x? Cela ne signifie pas qu'il est le premier, cela signifie seulement que ce particulier x ne divise pas
-
continuepasse à la prochaine itération de la boucle - mais vous voulez vraiment arrêter l'aidebreak
Voici votre code avec quelques corrections, elle imprime uniquement les nombres premiers:
import math
def main():
count = 3
while True:
isprime = True
for x in range(2, int(math.sqrt(count) + 1)):
if count % x == 0:
isprime = False
break
if isprime:
print count
count += 1
Pour la génération prime beaucoup plus efficace, voir le Crible d'Eratosthène, comme d'autres l'ont suggéré. Voici une belle mise en œuvre optimisée avec de nombreux commentaires:
# Sieve of Eratosthenes
# Code by David Eppstein, UC Irvine, 28 Feb 2002
# http://code.activestate.com/recipes/117119/
def gen_primes():
""" Generate an infinite sequence of prime numbers.
"""
# Maps composites to primes witnessing their compositeness.
# This is memory efficient, as the sieve is not "run forward"
# indefinitely, but only as long as required by the current
# number being tested.
#
D = {}
# The running integer that's checked for primeness
q = 2
while True:
if q not in D:
# q is a new prime.
# Yield it and mark its first multiple that isn't
# already marked in previous iterations
#
yield q
D[q * q] = [q]
else:
# q is composite. D[q] is the list of primes that
# divide it. Since we've reached q, we no longer
# need it in the map, but we'll mark the next
# multiples of its witnesses to prepare for larger
# numbers
#
for p in D[q]:
D.setdefault(p + q, []).append(p)
del D[q]
q += 1
Notez qu'il retourne un générateur.
Autres conseils
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'A 20 dans une liste. Je aurais pu utiliser Sieve 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+)\1+$').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 ... qui est en ligne avec la demande initiale de l'OP (maintenant six mois); et devrait être une solution tout à fait acceptable dans un cours « programmation 101 » ... D'où ce poste.
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 « force brute » est « assez vite » pour les nombres jusqu'à environ 16.000 sur les PC modernes sur (a pris environ 8 secondes sur ma boîte de 2GHz).
De toute évidence, cela pourrait se faire beaucoup plus efficace, en ne recalculant le primeness de chaque nombre pair, ou tout multiple de 3, 5, 7, etc pour chaque numéro unique ... Voir Eratosthène de Sieve (voir la mise en œuvre de eliben ci-dessus), ou même le crible d'Atkin si vous vous sentez particulièrement courageux et / ou fou.
caveat emptor: Je suis un noob python. S'il vous plaît ne prenez pas tout ce que je dis comme parole d'évangile.
A mon avis, il est toujours préférable de prendre l'approche fonctionnelle,
Je crée donc une fonction première à savoir si le nombre est premier ou ne pas utiliser alors en boucle ou tout autre lieu si nécessaire.
def isprime(n):
for x in range(2,n):
if n%x == 0:
return False
return True
Ensuite, exécutez une compréhension de liste simple ou expression générateur pour obtenir votre liste de premier,
[x for x in range(1,100) if isprime(x)]
Cela semble devoir-y, donc je vais donner un indice plutôt qu'une explication détaillée. Corrigez-moi si j'ai supposais mal.
Vous faites bien aussi loin que écoper quand vous voyez un même diviseur.
Mais vous imprimez « count » dès que vous voyez même un nombre qui ne divise pas en elle. 2, par exemple, ne divise pas uniformément dans 9. Mais cela ne fait pas 9 premier. Vous voudrez peut-être continuer jusqu'à ce que vous êtes sûr pas nombre dans les matches de gamme.
(comme d'autres ont répondu, un Sieve est beaucoup plus moyen efficace d'aller ... juste essayer de vous aider à comprendre pourquoi ce code spécifique ne fait pas ce que vous voulez)
Que diriez-vous si vous voulez calculer le premier 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 simple optimisation de seulement compte tenu des nombres impairs. Tout ce fait avec des courants paresseux (générateurs de python).
Utilisation: nombres premiers = list (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
Voici une version numpy de crible d'Eratosthène ayant à la fois la complexité correct (inférieur à tri d'un tableau de longueur n) et la 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]
synchronisations:
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
-
L'instruction continue semble erroné.
-
Vous voulez commencer à 2 parce que 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 sont pas Répartir le numéro que vous vérifiez. Dans ce cas, vous imprimerez le numéro que vous vérifiez tout moment que l'un des diviseurs possibles ne divise pas également le nombre.
Aussi, vous ne voulez pas utiliser une déclaration continue parce que continuer ne fera que pour vérifier le prochain diviseur possible lorsque vous avez déjà découvert que le numéro est un nombre 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
Il est assez rapide pour un grand nombre, car il ne vérifie contre les numéros déjà pour les premiers 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
utilisant des générateurs ici peut être souhaité pour l'efficacité.
Et juste pour la référence, au lieu de dire:
one = 1
while one == 1:
# do stuff
vous pouvez dire simplement:
while 1:
#do stuff
Vous pouvez créer une liste de nombres premiers compréhensions d'une manière assez élégante. Tiré 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 « tous » au lieu de la double négation (un peu plus facile à lire, mais je pense 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 parcourt x à portée de (2, 100) et la cueillette que ceux qui n'ont pas mod == 0 pour tout t dans la plage (2, x)
Une autre façon est probablement peuplant les nombres premiers que 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.
Voici 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 souhaitez trouver tous les nombres premiers dans une gamme que vous pourriez 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.
SORTIE:
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
Utilisation de générateur:
def primes(num):
if 2 <= num:
yield 2
for i in range(3, num + 1, 2):
if all(i % x != 0 for x in range(3, int(math.sqrt(i) + 1))):
yield i
Utilisation:
for i in primes(10):
print(i)
2, 3, 5, 7
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
