Semplice generatore di numeri primi in Python

Question

Qualcuno potrebbe dirmi cosa sto facendo di sbagliato con questo codice?In ogni caso sta semplicemente stampando "conteggio".Voglio solo un generatore primo molto semplice (niente di speciale).

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

Ci sono alcuni problemi:

• Perché di stampare conteggio quando non dividere per x? Ciò non significa che la fondamentale, significa solo che questo particolare x non dividerlo
• continue si sposta sulla prossima iterazione del ciclo - ma si vuole veramente fermarla con break

Ecco il codice con alcune correzioni, esso stampa solo numeri primi:

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

Per la generazione privilegiata molto più efficiente, vedere la crivello di Eratostene, come altri hanno suggerito. Ecco una bella, implementazione ottimizzata con molti commenti:

# 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

Si noti che restituisce un generatore.

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]

Ci metteremo tutti i numeri primi fino a 20 in un elenco. Avrei potuto usare Crivello di Eratostene, ma lei ha detto si desidera qualcosa di molto semplice. ;)

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 è potente:

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]

Per verificare se un numero è primo:

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

Answer 6

Ecco un semplice (2.6.2 Python), soluzione ... che è in linea con richiesta originale del PO (ora sei mesi di età); e dovrebbe essere una soluzione perfettamente accettabile in ogni "programmazione 101" corso ... Quindi questo messaggio.

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

Questo semplice metodo "forza bruta" è "abbastanza veloce" per i numeri fino a circa circa 16.000 sulla moderna PC (ha circa 8 secondi sulla mia macchina 2 GHz).

Ovviamente, questo potrebbe essere fatto in modo più efficiente, non ricalcolando il primeness di ogni numero pari, o ogni multiplo di 3, 5, 7, ecc per ogni singolo numero ... Vedere la Crivello di Eratostene (vedi implementazione del eliben sopra), o anche il Crivello di Atkin se vi sentite particolarmente coraggiosi e / o un pazzo.

caveat emptor: io sono un noob pitone. Si prega di non prendere quello che dico come vangelo.

Answer 7

Per me è sempre meglio prendere l'approccio funzionale,

Quindi creo una funzione prima di scoprire se il numero è primo o poi non utilizzarlo in loop o altro luogo, se necessario.

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

Quindi eseguire una semplice espressione di lista o di un generatore per ottenere l'elenco delle prime,

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

Answer 8

Questo sembra compiti a casa-y, quindi dovrò dare un suggerimento, piuttosto che una spiegazione dettagliata. Mi corregga se ho assunto sbagliato.

Si sta facendo bene per quanto riguarda il salvataggio di quando si vede un ancora divisore.

Ma si sta stampando 'count', non appena si vede anche una numero che non divide in esso. 2, per esempio, non dividere in modo uniforme in 9. Ma questo non fa 9 un numero primo. Si potrebbe desiderare di andare avanti fino a quando si è sicuri non numero nelle partite di gamma.

(come altri hanno risposto, a Sieve è un modo molto più efficiente di andare ... solo cercando di aiutare a capire il motivo per cui questo codice specifico non sta facendo quello che si vuole)

Answer 9

Come su questo se si vuole calcolare direttamente il primo:

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

Un altro semplice esempio, con una semplice ottimizzazione di considerare solo i numeri dispari. Tutto fatto con flussi pigri (generatori Python).

utilizzo: i numeri primi = 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

Ecco una versione numpy di Sieve of Eratosthenes che ha sia una buona complessità (inferiore all'ordinamento di un array di lunghezza n) che una vettorizzazione.

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]

Tempi:

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

• L'istruzione continue sembra sbagliato.

• Si vuole iniziare a 2 perché 2 è il primo numero primo.

• Si può scrivere "while True:" per avere un ciclo infinito

.

Answer 13

È necessario fare in modo che tutti i possibili divisori non in modo uniforme dividere il numero si sta controllando. In questo caso si stampare il numero si sta controllando ogni momento solo uno dei possibili divisori non in modo uniforme dividere il numero.

Inoltre non si vuole utilizzare un'istruzione continue perché una continua sarà solo causare a controllare il prossimo possibile divisore quando hai già scoperto che il numero non è un numero primo.

Answer 14

Ecco quello che ho:

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

E 'abbastanza veloce per grandi numeri, in quanto solo i controlli contro i numeri già principali per divisori di un numero.

Ora, se si desidera generare un elenco di numeri primi, si può fare:

# 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

utilizzando generatori qui potrebbe desiderare per l'efficienza.

E solo per riferimento, invece di dire:

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

si può semplicemente dire:

while 1:
    #do stuff

Answer 15

È possibile creare una lista di numeri primi che utilizzano list comprehension in maniera piuttosto elegante. Tratto da qui:

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

Simile a user107745, ma utilizzando 'all' invece di doppia negazione (un po 'più leggibile, ma credo che a parità di prestazioni):

import math
[x for x in xrange(2,10000) if all(x%t for t in xrange(2,int(math.sqrt(x))+1))]

Fondamentalmente itera sulla x nella gamma di (2, 100) e solo quelli che non hanno == mod 0 per ogni t nella gamma di raccolta (2, x)

Un altro modo è probabilmente solo popolando i numeri primi, come andiamo:

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 è una libreria Python per la matematica simbolica. Esso fornisce diverse funzioni per generare numeri primi.

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. 

Ecco alcuni esempi.

>>> 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 si voleva trovare tutti i numeri primi in una serie che si potrebbe fare questo:

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 aggiungere while its <= e il numero per l'intervallo.
USCITA:
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

Utilizzando generatore:

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

Utilizzo:

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

Per me, la soluzione qui di seguito sembra semplice e facile da seguire.

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