Generator Prime simples em Python

Question

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

Answer 1

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 usando break

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.

Answer 2

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

Answer 3

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

Answer 4

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]

Answer 5

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

Answer 6

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.

Answer 7

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

Answer 8

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)

Answer 9

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

Answer 10

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

Answer 11

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

Answer 12

• 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

Answer 13

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.

Answer 14

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

Answer 15

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]

Answer 16

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 17

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

Answer 18

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 19

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]

Answer 20

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

Answer 21

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

Answer 22

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 23

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