El primer generador simple en Python
https://stackoverflow.com/questions/567222
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
¿Puede alguien decirme lo que estoy haciendo mal con este código? Sólo está imprimiendo 'contar' de todos modos. Sólo quiero un principal generador muy simple (nada de fantasía).
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
Solución
Hay algunos problemas:
- ¿Por qué imprimir recuento cuando no dividió por x? Esto no quiere decir que es primordial, sólo significa que esta x particular no dividirlo
-
continuemueve a la siguiente iteración del bucle - pero que realmente quieren detenerlo usandobreak
Aquí está el código con algunas correcciones, imprime solamente los números primos:
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
Para la generación privilegiada mucho más eficiente, ver la Criba de Eratóstenes, como han sugerido otros. Aquí está un agradable, implementación optimizada con muchos comentarios:
# 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
Observe que devuelve un generador.
Otros consejos
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]
Vamos a conseguir todos los números primos hasta 20 en una lista. Podría haber usado criba de Eratóstenes, pero que dicho quieres algo muy simple. ;)
print [x for x in range(2,100) if not [t for t in range(2,x) if not x%t]]
re es de gran alcance:
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]
Para probar si un número es primo:
>>> 541 in primes(541)
True
>>> 543 in primes(543)
False
Aquí hay un sencilla (2.6.2 Python) solución ... que está en línea con la solicitud original del OP (ahora seis meses de edad); y debe ser una solución perfectamente aceptable en cualquier "programación 101" por supuesto ... Por lo tanto este 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
Este sencillo método de "fuerza bruta" es "lo suficientemente rápido" para los números hasta aproximadamente unos 16.000 en la PC moderna de (tardó aproximadamente 8 segundos en mi caja de 2 GHz).
Obviamente, esto se podría hacer mucho más eficiente, al no volver a calcular la primalidad de cada número par, o cada múltiplo de 3, 5, 7, etc para cada número de un solo ... Ver la criba de Eratóstenes (ver aplicación de eliben arriba), o incluso la criba de Atkin si te sientes particularmente valiente y / o loco.
caveat.emptor: Soy un novato pitón. Por favor, no tomar cualquier cosa que digo como un evangelio.
Para mi opinión siempre es mejor tomar el enfoque funcional,
Así se crea una función de primera para averiguar si el número es primo o no luego usarlo en bucle o de otro lugar que sea necesario.
def isprime(n):
for x in range(2,n):
if n%x == 0:
return False
return True
A continuación, ejecute una expresión simple lista por comprensión o generador para obtener su lista de primer,
[x for x in range(1,100) if isprime(x)]
Esto parece tarea-y, así que voy a dar una pista en lugar de una explicación detallada. Corregir si me he asumido mal.
Lo estás haciendo bien en cuanto a rescatar a cuando vea un divisor par.
Pero si imprime 'count' tan pronto como se ve incluso un cantidad que no divide en él. 2, por ejemplo, no divisible por 9. Pero eso no significa que 9 un número primo. Es posible que desee seguir adelante hasta que esté seguro de no número en los partidos de rango.
(como han respondido, a Sieve es una manera mucho más eficiente que ir ... tratando de ayudar a entender por qué este código específico no está haciendo lo que quiere)
¿Qué hay de esto si desea calcular la óptima directamente:
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
Otro ejemplo sencillo, con una simple optimización de considerar sólo los números impares. Todo hecho con las corrientes perezosas (generadores pitón).
uso: primos = lista (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
Aquí es una versión numpy de criba de Eratóstenes que tiene tanto la complejidad bien (clasificación más baja que una matriz de longitud n) y vectorización.
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]
Los tiempos:
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
-
La sentencia continue se ve mal.
-
¿Quieres empezar a las 2 porque 2 es el primer número primo.
-
Puede escribir "while True:" para conseguir un bucle infinito
.
Es necesario asegurarse de que todos los divisores posibles no se dividen de manera uniforme el número que está comprobando. En este caso donde se imprime el número que está comprobando cualquier momento sólo uno de los posibles divisores no uniformemente dividir el número.
También usted no desea utilizar una sentencia continue continuar porque un sólo va a hacer que se compruebe la siguiente divisor posible cuando ya has descubierto que el número no es un número primo.
Esto es lo que tengo:
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
Es bastante rápido para un gran número, ya que sólo cheques contra números ya principales para divisores de un número.
Ahora bien, si desea generar una lista de números primos, que puede hacer:
# 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
utilizando generadores de aquí podría ser deseable para la eficiencia.
Y apenas para la referencia, en lugar de decir:
one = 1
while one == 1:
# do stuff
se puede decir simplemente:
while 1:
#do stuff
Puede crear una lista de números primos usando listas por comprensión de una manera bastante elegante. Tomado de aquí:
>>> 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
Al igual que en user107745, pero el uso de 'todos' en lugar de la doble negación (un poco más fácil de leer, pero creo mismo rendimiento):
import math
[x for x in xrange(2,10000) if all(x%t for t in xrange(2,int(math.sqrt(x))+1))]
Básicamente se itera sobre la x en el rango de (2, 100) y sólo aquellos que no tienen == mod 0 para todo t en el rango de picking (2, x)
Otra forma es probable que sólo poblando los números primos como vamos:
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 es una biblioteca de Python para las matemáticas simbólicas. Proporciona varias funciones para generar números primos.
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.
Estos son algunos ejemplos.
>>> 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 desea encontrar todos los números primos en una gama que podría hacer esto:
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)
Sólo tiene que añadir while its <= y su número de la gama.
SALIDA:
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
El uso del generador:
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
Uso:
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
Para mí, la solución de abajo parece simple y fácil de seguir.
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
