python - how - plotly library

Simple Prime Generator en Python

Question

¿Podría alguien decirme qué estoy haciendo mal con este código? Simplemente está imprimiendo ''contar'' de todos modos. Solo quiero un generador de primos muy simple (nada sofisticado).

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

Answer 1

¿Qué tal si quieres calcular el primo 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

Answer 2

Aquí hay una solución simple (Python 2.6.2) ... que está en línea con la solicitud original del OP (ahora tiene seis meses); y debería ser una solución perfectamente aceptable en cualquier curso de "programación 101" ... De ahí esta publicación.

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 simple método de "fuerza bruta" es "lo suficientemente rápido" para números de aproximadamente 16,000 en PC modernas (tomó aproximadamente 8 segundos en mi caja de 2GHz).

Obviamente, esto podría hacerse mucho más eficientemente, al no recalcular la excelencia de cada número par, o cada múltiplo de 3, 5, 7, etc. para cada número ... Ver el en.wikipedia.org/wiki/Sieve_of_Eratosthenes (ver la implementación de eliben más arriba), o incluso el Sieve of Atkin si te sientes particularmente valiente y / o loco.

Caveat Emptor: Soy un novato de Python. Por favor no tomes nada que diga como evangelio.

Answer 3

Aquí hay una versión numpy de Sieve of Eratosthenes que tiene una complejidad aceptable (más baja que ordenar 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]

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

Answer 4

Debe asegurarse de que todos los divisores posibles no dividan de manera uniforme el número que está comprobando. En este caso, imprimirá el número que está comprobando en cualquier momento, solo uno de los posibles divisores no divide el número de manera pareja.

Además, no desea utilizar una instrucción de continuación porque un continuar solo hará que verifique el siguiente divisor posible cuando ya haya descubierto que el número no es primo.

Answer 5

En mi opinión, siempre es mejor tomar el enfoque funcional,

Así que creo una función primero para averiguar si el número es primo o no, luego utilícelo en bucle u otro lugar según sea necesario.

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

Luego ejecute una simple lista de comprensión o expresión del generador para obtener su lista de primos,

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

Answer 6

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 números grandes, ya que solo comprueba contra números primos ya existentes para los divisores de un número.

Ahora, si quieres generar una lista de números primos, puedes 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

el uso de generadores aquí podría ser deseable para la eficiencia.

Y solo como referencia, en lugar de decir:

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

simplemente puedes decir:

while 1:
#do stuff

Answer 7

Esto parece tarea-y, así que daré una pista en lugar de una explicación detallada. Corrígeme si he asumido el error.

Lo estás haciendo bien en cuanto a rescatar cuando ves un divisor par.

Pero está imprimiendo ''conteo'' apenas ve un número que no se divide en él. 2, por ejemplo, no se divide de manera uniforme en 9. Pero eso no convierte a 9 en el mejor. Es posible que desee seguir hasta que esté seguro de que no hay ningún número en el rango que coincida.

(como otros han respondido, un Sieve es una forma mucho más eficiente de ir ... solo estoy tratando de ayudarte a entender por qué este código específico no está haciendo lo que quieres)

Answer 8

Hay algunos problemas:

• ¿Por qué imprimen cuenta cuando no se dividió por x? No significa que sea primo, solo significa que esta x particular no lo divide
• continue moviéndose a la siguiente iteración de bucle - pero realmente quieres detenerlo usando break

Aquí está su código con algunas correcciones, imprime solo 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 una generación principal mucho más eficiente, vea el Tamiz de Erastothenes, como otros han sugerido. Aquí hay una implementación agradable y 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

Tenga en cuenta que devuelve un generador.

Answer 9

Otro ejemplo simple, con una optimización simple de solo considerando números impares. Todo hecho con flujos perezosos (generadores de pitón).

Uso: primes = 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

Answer 10

Para mí, la siguiente solución 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

Answer 11

Puede crear una lista de números primos utilizando listas de comprensión de una manera bastante elegante. Tomado desde here:

>>> 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]

Answer 12

Si quieres encontrar todos los números primos en un rango, puedes 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)

Solo agregue while its <= y su número para el rango.
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

Answer 13

Similar al user107745, pero usando ''todo'' en lugar de doble negación (un poco más legible, pero creo que el 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 itera sobre la x en el rango de (2, 100) y selecciona solo aquellas que no tienen mod == 0 para todo t en el rango (2, x)

Otra forma es probablemente llenar los números primos a medida que avanzamos:

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))

Answer 14

re es poderoso:

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]

Answer 15

SymPy es una biblioteca de Python para matemática simbólica. 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.

Aquí hay unos 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]

Answer 16

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

Answer 17

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

Answer 18

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]

Tendremos todos los números primos hasta 20 en una lista. Podría haber usado Sieve of Eratosthenes pero dijiste que querías algo muy simple. ;)

Answer 19

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 primordial:

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

Answer 20

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

Answer 21

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

Answer 22

• La instrucción continue se ve mal.

• Desea comenzar en 2 porque 2 es el primer número primo.

• Puede escribir "while True:" para obtener un ciclo infinito.