Numero casuale primo in python

Question

Attualmente ho impostato ↓ come funzione randprime(p,q). C'è un modo per condensare questo, tramite qualcosa come un gene o listcomp? Ecco la mia funzione:

n = randint(p, q) 
while not isPrime(n): 
    n = randint(p, q) 

Answer 1

È meglio solo generare l'elenco di numeri primi e quindi scegliere da quella linea. Così com'è, con il tuo codice c'è la sottile possibilità che colpirà un ciclo infinito, o se non ci sono numeri primi nell'intervallo o se randint seleziona sempre un non-prime, quindi il ciclo while non finirà mai.

Quindi questo è probabilmente più breve e meno fastidioso:

import random 
primes = [i for i in range(p,q) if isPrime(i)] 
n = random.choice(primes) 

L'altro vantaggio di questo è che non c'è alcuna possibilità di stallo se non ci sono numeri primi nell'intervallo. Come detto questo può essere lento a seconda del campo, quindi sarebbe più veloce se memorizzato nella cache i numeri primi prima del tempo:

# initialising primes 
minPrime = 0 
maxPrime = 1000 
cached_primes = [i for i in range(minPrime,maxPrime) if isPrime(i)] 

#elsewhere in the code 
import random 
n = random.choice([i for i in cached_primes if p<i<q]) 

Anche in questo caso, ulteriori ottimizzazioni sono possibili, ma sono molto dipende dal codice vero e proprio .. e tu sai cosa dicono di ottimizzazioni premature.

Answer 2

next(i for i in itertools.imap(lambda x: random.randint(p,q)|1,itertools.count()) if isPrime(i)) 

Questo inizia con itertools.count() - questo dà un insieme infinito.

Ogni numero è mappato a un nuovo numero casuale nell'intervallo, da itertools.imap(). imap è come una mappa, ma restituisce un iteratore, piuttosto che una lista - non vogliamo generare una lista di numeri casuali inifiniti!

Quindi, il primo numero corrispondente viene trovato e restituito.

Funziona in modo efficiente, anche se p e q sono molto distanti - ad es. 1 e 10 ** 30, che non generano una lista completa!

A proposito, questo non è più efficiente del tuo codice sopra, ed è molto più difficile da capire a colpo d'occhio - ti preghiamo di avere qualche considerazione per il prossimo programmatore di dover leggere il tuo codice, e fallo come hai fatto sopra. Quel programmatore potrebbe essere tu tra sei mesi, quando hai dimenticato cosa doveva fare questo codice!

P.S - in pratica, si potrebbe voler sostituire count() con xrange (NON range!) Ad es. xrange((p-q)**1.5+20) non fare più di quel numero di tentativi (bilanciati tra test limitati per intervalli piccoli e grandi gamme, e non ha più dell'1/2% di possibilità di fallire se potesse riuscire), altrimenti, come è stato suggerito in un altro post, potrebbe loop per sempre.

PPS - miglioramento: sostituito random.randint(p,q) con random.randint(p,q)|1 - questo rende il codice di due volte più efficiente, ma elimina la possibilità che il risultato sarà 2.

Answer 3

Quindi sarebbe bello se si potesse usare un iteratore per dare il numeri interi da p a q in ordine casuale (senza sostituzione). Non sono stato in grado di trovare un modo per farlo. Quanto segue fornirà numeri interi casuali in quell'intervallo e salterà qualsiasi cosa che sia già stata testata.

import random 
fail = False 
tested = set([]) 
n = random.randint(p,q) 
while not isPrime(n): 
    tested.add(n) 
    if len(tested) == p-q+1: 
     fail = True 
     break 
    while n in s: 
     n = random.randint(p,q) 

if fail: 
    print 'I failed' 
else: 
    print n, ' is prime' 

Il grande vantaggio di questo è che se dire la gamma si sta testando è solo (14,15), il codice sarebbe correre per sempre.Questo codice è garantito per produrre una risposta se esiste un tale primo e dire che non ce n'è uno se tale primo non esiste. Ovviamente puoi renderlo più compatto, ma sto cercando di mostrare la logica.