Generator Prime simples em Python
Pergunta
Alguém poderia me dizer o que estou fazendo de errado com esse código? É apenas imprimir 'contar' de qualquer maneira. Eu só quero um gerador primordial muito simples (nada extravagante).
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
Solução
Existem alguns problemas:
- Por que você imprimir contagem quando não dividir por x? Isso não significa que é prime, que significa apenas que este particular x não dividi-lo
-
continue
move para a próxima iteração do loop - mas você realmente quer pará-lo usandobreak
Aqui está seu código com algumas correções, ele imprime única 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 muito mais eficiente geração primária, ver a Sieve de Erastothenes, como já foi sugerido. Aqui está um belo, implementação otimizada com muitos comentários:
# 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
Note que ele retorna um gerador.
Outras dicas
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 ter todos os números primos upto 20 em uma lista. Eu poderia ter usado Crivo de Eratóstenes, mas você disse você quer algo muito simples. ;)
print [x for x in range(2,100) if not [t for t in range(2,x) if not x%t]]
re é 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]
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 testar se um número é primo:
>>> 541 in primes(541)
True
>>> 543 in primes(543)
False
Aqui está um (2.6.2 Python) solução ... simples, que está em linha com o pedido original do OP (agora seis meses de idade); e deve ser uma solução perfeitamente aceitável em qualquer "programação 101" Claro ... Por isso 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 método simples "força bruta" é "suficientemente rápido" para os números até cerca de cerca de 16.000 em PCs modernos (levou cerca de 8 segundos em minha caixa de 2GHz).
Obviamente, isso poderia ser feito muito mais eficiente, por não recalcular o primeness de cada número par, ou a cada múltiplo de 3, 5, 7, etc para cada número único ... Veja Crivo de Eratóstenes (veja implementação do eliben acima), ou até mesmo o Crivo de Atkin Se você estiver sentindo particularmente corajoso e / ou louco.
advertência Emptor: Eu sou um noob python. Por favor, não tome qualquer coisa eu digo como um evangelho.
Para minha opinião é sempre melhor tomar a abordagem funcional,
Então eu criar uma função de primeira para descobrir se o número é primo ou não, em seguida, usá-lo em loop ou outro lugar, se necessário.
def isprime(n):
for x in range(2,n):
if n%x == 0:
return False
return True
Em seguida, execute uma simples lista de compreensão ou gerador de expressão para obter a sua lista de primordial,
[x for x in range(1,100) if isprime(x)]
Isto parece dever de casa-y, por isso vou dar uma dica ao invés de uma explicação detalhada. Corrija-me se eu já assumiu errado.
Você está indo bem, tanto quanto socorrer quando você vê um divisor mesmo.
Mas você está imprimindo 'count', logo que você vê até mesmo um número que não se divide para ele. 2, por exemplo, não divide uniformemente em 9. Mas isso não faz 9 a prime. Você pode querer continuar até que você tem certeza de não número nos jogos alcance.
(como outros já respondeu, a Sieve é ??uma maneira muito mais eficiente para ir ... apenas tentando ajudá-lo a entender por que esse código específico não está fazendo o que você quer)
Como sobre isso, se você quiser calcular a privilegiada 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
Outro exemplo simples, com um simples otimização de considerar apenas os números ímpares. Tudo feito com riachos preguiçosos (geradores de python).
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
Aqui é uma versão numpy de Crivo de Eratóstenes tendo ambos complexidade ok (inferior a triagem uma matriz de comprimento n) e vectorização.
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]
Timings:
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
-
A continuar olhares declaração errada.
-
Você quer começar em 2 porque 2 é o primeiro número primo.
-
Você pode escrever "while True:". Para obter um loop infinito
Você precisa ter certeza de que todos os divisores possíveis não dividir igualmente o número que você está verificando. Neste caso, você vai imprimir o número que você está verificando qualquer momento apenas uma das possíveis divisores não dividir igualmente o número.
Além disso, você não quer usar uma instrução continuar porque a continuar só vai causar-lhe a verificar a próxima divisor possível quando você já descobriu que o número não é primo.
Aqui está o que eu tenho:
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
É muito rápido para grandes números, como ele só verifica contra números já privilegiados para divisores de um número.
Agora, se você deseja gerar uma lista de números primos, você pode fazer:
# 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
usando geradores aqui pode ser desejado para a eficiência.
E apenas para referência, em vez de dizer:
one = 1
while one == 1:
# do stuff
você pode simplesmente dizer:
while 1:
#do stuff
Você pode criar uma lista de números primos usando compreensões lista de uma forma bastante elegante. Tomado de aqui:
>>> 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
Semelhante ao user107745, mas usando 'all' em vez de dupla negação (um pouco mais legível, mas acho que mesmo desempenho):
import math
[x for x in xrange(2,10000) if all(x%t for t in xrange(2,int(math.sqrt(x))+1))]
Basicamente, ele itera sobre o x na faixa de (2, 100) e escolher apenas aqueles que não têm mod == 0 para todo t no intervalo (2, x)
Outra maneira é provavelmente apenas preencher os números primos como vamos nós:
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 é uma biblioteca Python para matemáticas simbólicas. Ele fornece várias funções para gerar 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.
Aqui estão alguns exemplos.
>>> 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]
Se você quiser encontrar todos os números primos em um intervalo que você poderia fazer isso:
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)
Basta adicionar while its <=
e seu número para o intervalo.
SAÍDA:
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
Usando o gerador:
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 mim, o abaixo solução parece simples e 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