Aléatoire de Nombre premier en python

J'ai actuellement ↓ définir comme mon randprime(p,q) fonction. Est-il possible de condenser ce, par quelque chose comme un genexp ou listcomp? Voici ma fonction:

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

Il semble que ce serait mieux pour générer une liste de nombres premiers entre p et q et puis choisir un au hasard à partir de cette liste.
Vous pouvez augmenter vos chances d'un nombre premier en définissant le bit de poids faible à 1, ce qui rend étrange - il est seul à même le premier, qui est de 2. En fait, tous les nombres premiers autres que 2 et 3 sont soit celui ci-dessous, ou de l'une au-dessus d'un multiple de six.
Je déteste quand quelqu'un downvote une question sans lui dire pourquoi, parce que l'OP ne peuvent pas le réparer si il ne sait pas ce qui est mal.
qui dépend de la taille de p & q. Pour un grand nombre, ce qui serait plus efficace. Aussi, si vous êtes en train de faire un numéro de tamis (moyen le plus facile de générer des nombres premiers), alors vous avez besoin pour commencer à 1.
Merci à tous, la question manque de spécificité et une grande partie de l'arrière-et-vient ici les résultats de cette. Pourriez-vous vous blâmer qu'à la place des autres answerers?

OriginalL'auteur PolarBearITS | 2015-01-08

4

Il est préférable de simplement générer la liste des nombres premiers, puis choisissez partir de cette ligne.
Comme il est, avec votre code est la petite chance qu'il sera frappé d'une boucle infinie, soit si il n'y a pas de nombres premiers dans l'intervalle ou si randint choisit toujours un non-premier puis le while boucle n'aura jamais de fin.

Donc c'est probablement plus courte et moins gênant:
```
import random
primes = [i for i in range(p,q) if isPrime(i)]
n = random.choice(primes)
```
L'autre avantage de cela est qu'il n'ya aucune chance de blocage si il n'y a pas de nombres premiers dans l'intervalle. Comme l'a déclaré cela peut être long en fonction de la gamme, de sorte qu'il serait plus rapide si vous en cache les nombres premiers à l'avance:
```
# 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])
```
De nouveau, des optimisations sont possibles, mais dépend beaucoup de votre propre code... et vous savez ce qu'ils disent à propos de prématuré d'optimisations.

Cela peut être une très mauvaise idée si p et q sont de l'ordre de 10**10, qui est une chose raisonnable à essayer si vous êtes en train de penser au sujet de cryptage.
Je suppose que si il y a des nombres premiers entre p et q il va se bloquer pour vous.
Eh bien, sans doute qu'ils allaient être mise en cache de la isPrime vérifier, ou d'avoir une prédéfinis liste de travail.
pas nécessairement. Lorsque vous travaillez avec de grands nombres premiers (par exemple, pour le chiffrement RSA), de la manière habituelle est de vérifier les petits nombres, et ensuite utiliser une méthode statistique - voir en.wikipedia.org/wiki/Primality_test#Probabilistic_tests (depuis un test complet prendrait trop d'années pour une définition de 2 048 bits en premier) - chaque essai sur un premier réussira, et chaque essai sur un non-prime a 50% de chances de montrer que le nombre n'est pas premier. Décider de la façon de faible probabilité que vous voulez, et lancez le nombre de tests.
Les gens sont simplement de faire sauvages hypothèses sur le chiffrement et fou grand nombre. Ce pourrait être le premier cycle première année de programmation de la question.

OriginalL'auteur
0

De sorte qu'il serait génial si vous pouviez utiliser un itérateur pour donner les entiers de p à q dans un ordre aléatoire (sans remplacement). Je n'ai pas été en mesure de trouver un moyen de le faire. La suite donnera entiers aléatoires dans cette gamme et d'ignorer tout ce qu'il est testé déjà.
```
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'
```
Le gros avantage, c'est que si par exemple la gamme que vous effectuez le test est juste (14,15), votre code peut toujours courir. Ce code est garanti pour produire une réponse si un tel premier existe, et vous dire il n'y a pas si un tel premier n'existe pas. Vous pouvez bien évidemment le rendre plus compact, mais j'essaie de montrer la logique.

Oui, mais le mien sera fini, si, étant donné une série sans un nombre premier, et de l'exécuter en beaucoup moins de temps si une plage avec seulement quelques nombres premiers.
code de l'OP est de 3 lignes, mais il va se bloquer si il n'y a pas de nombres premiers entre p et q, de sorte qu'il est dangereux.
C'était moi, et j'ai voté vous vers le bas parce que votre réponse, tout en introduisant quelque chose d'utile, est à l'EXACT OPPOSÉ de ce qui était demandé - Is there any way to condense this. J'ai fait donner le crédit que la partie n'était pas la mienne. Ce n'était pas la base de ma réponse, seulement une note de bas de page. Vous êtes les bienvenus pour intégrer mon code dans votre réponse comme une note de bas de page (ou des idées de là).
Beaux - votre code est sur une ligne, mais c'est encore près de 2 fois plus de caractères que le code d'origine, nécessite l'importation itertools, et ne permettent pas de résoudre le bug. Est que les résumés? Prendre le morceau de mon code d'éliminer le bug et mon code est fondamentalement la même longueur (en caractères) que le vôtre.
Mon code fonctionne avec p=14,q=15 et est beaucoup plus courte, et n'a pas de blocages...

OriginalL'auteur Joel
-1
```
next(i for i in itertools.imap(lambda x: random.randint(p,q)|1,itertools.count()) if isPrime(i))
```
Cela commence avec itertools.comte (le) - ce qui donne un ensemble infini.

Chaque nombre est associé à un nouveau nombre aléatoire dans l'intervalle, par itertools.imap(). imap est comme carte, mais retourne un itérateur, plutôt qu'une liste - nous ne voulons pas de générer une liste de inifinite nombres aléatoires!

Ensuite, le premier numéro correspondant est trouvé, et s'en retourna.

Fonctionne de manière efficace, même si p et q sont de très loin - par exemple 1 et 10**30, la génération d'une liste complète va pas le faire!

Par la manière, ce n'est pas plus efficace que votre code ci-dessus, et qui est beaucoup plus difficile à comprendre en un coup d'œil s'il vous plaît avoir une certaine considération pour la prochaine programmeur d'avoir à lire votre code, et il suffit de faire comme vous l'avez fait ci-dessus. Que programmeur peut être vous dans six mois, lorsque vous avez oublié ce que ce code est censé faire!

P. S - dans la pratique, vous pouvez remplacer la fonction count() avec xrange (PAS de plage!) par exemple, xrange((p-q)**1.5+20) rien faire de plus que ce nombre de tentatives (équilibré entre les tests limités pour les petites plages et de grandes plages, et n'a pas plus de 1/2% de chance d'échouer si elle pourrait réussir), sinon, comme il a été suggéré dans un autre post, vous pourriez boucle pour toujours.

PPS - amélioration: remplacé random.randint(p,q) avec random.randint(p,q)|1 - cela rend le code moins deux fois plus efficace, mais élimine la possibilité que le résultat sera 2.

J'ai considéré q-p, et puis simplifié de p, puis p**2. Ma dernière réponse (décidé) est (q-p)**2. q-p est probablement pas assez; Si vous avez deux nombres et l'un d'eux est premier (par exemple q=18 et p=19), alors vous avez 25% de chance d'échec. Lorsque la distance augmente, les chances de couvrir tous les numéros de la plage diminue (échantillonnage range nombres aléatoires dans range).
Ayant fait un peu de chasse, un très mauvais scénario est de choisir p=1425172824437699411, et q=p+1475; dans cette gamme de nombres, il n'est qu'un premier (et 1475 non premiers). Chacun a un 1475/1476 chance d'être un non-prime, de sorte que même 1476 tentatives de 37% de chance d'échouer.
Un autre calcul montre que (q-p)**2 tente peut-être pas assez - pour q=p+1 (p ou q est premier), il y a 6% de chance d'échec que beaucoup (=4) des tests. Je vais revoir ma réponse à (q-p)**2+20, qui ne sera que légèrement plus lent, et de mieux travailler pour de petits nombres.

OriginalL'auteur AMADANON Inc.

Vous devez vous connecter pour publier un commentaire.