python nombres premiers Crible d'Eratosthène

Salut quelqu'un peut me dire comment faire pour mettre en œuvre Crible d'Eratosthène à l'intérieur de ce code pour le faire rapidement? De l'aide sera vraiment apprécié si vous pouvez le compléter avec des tamis. Je suis vraiment à avoir de la difficulté à le faire dans ce code.

#!/usr/bin/env python
import sys
T=10 #no of test cases
t=open(sys.argv[1],'r').readlines()
import math
def is_prime(n):
if n == 2:
return True
if n%2 == 0 or n <= 1:
return False
sqr = int(math.sqrt(n)) + 1
for divisor in range(3, sqr, 2):
if n%divisor == 0:
return False
return True
#first line of each test case
a=[1,4,7,10,13,16,19,22,25,28]
count=0
for i in a:
b=t[i].split(" ")
c=b[1].split("\n")[0]
b=b[0]
for k in xrange(int(b)):
d=t[i+1].split(" ")
e=t[i+2].split(" ")
for g in d:
for j in e:
try:
sum=int(g)+int(j)
p=is_prime(sum)         
if p==True:
count+=1
print count
else:
pass
except:
try:
g=g.strip("\n")
sum=int(g)+int(j)
p=is_prime(sum)
if p==True:
count+=1
print count
else:
pass
except:
j=j.strip("\n")
sum=int(g)+int(j)
p=is_prime(sum)
if p==True:
count+=1
print count
else:
pass
print "Final count"+count

connexes: le plus Rapide moyen de la liste de tous les nombres premiers en dessous de N en python

OriginalL'auteur user2876096 | 2013-10-13

12

Un vieux truc pour excès de vitesse tamis en Python est d'utiliser de fantaisie 😉 liste tranche de notation, comme ci-dessous. Il utilise Python 3. Les changements nécessaires pour Python 2 sont à noter dans les commentaires:
```
def sieve(n):
"Return all primes <= n."
np1 = n + 1
s = list(range(np1)) # leave off `list()` in Python 2
s[1] = 0
sqrtn = int(round(n**0.5))
for i in range(2, sqrtn + 1): # use `xrange()` in Python 2
if s[i]:
# next line:  use `xrange()` in Python 2
s[i*i: np1: i] = [0] * len(range(i*i, np1, i))
return filter(None, s)
```
En Python 2, cela renvoie une liste; en Python 3 un itérateur. Ici sous Python 3:
```
>>> list(sieve(20))
[2, 3, 5, 7, 11, 13, 17, 19]
>>> len(list(sieve(1000000)))
78498
```
Ces deux fonctionnent en un clignement de paupières. Étant donné que, voici comment construire une is_prime fonction:
```
primes = set(sieve(the_max_integer_you_care_about))
def is_prime(n):
return n in primes
```
C'est le set() partie qui le rend rapide. Bien sûr, la fonction est si simple que vous auriez probablement souhaitez écrire:
```
if n in primes:
```
directement au lieu de vous embêter avec:
```
if is_prime(n):
```
Merci pour la réponse, mais maintenant, quand les nombres premiers sont générés. ils ne sont pas comparées à la somme des nombres dans la liste afin de l'ensemble du code est plus rapide.
le code est plus rapide que d'avant merci beaucoup. Mais la somme de la partie et de les comparer, c'est encore lent 🙁
si vous avez besoin de plus d'aide, je pense que vous devriez ouvrir une nouvelle question, en montrant le code exact que vous êtes à l'aide de maintenant. Ce question était à propos de l'aide d'un tamis, et a déjà été répondu 😉
merci je l'ai eu à travailler. Maintenant, il résout 50000x50000 listes en 7 minutes 🙂 Merci beaucoup à tous pour l'aide.
Yadav, mieux vaut prévenir que guérir. Par exemple, considérons n=169. L'Exponentiation est mis en œuvre par la prise d'un logarithme sous les couvertures, en multipliant par le pouvoir, et puis en soulevant la base du logarithme à ce résultat. En fonction de la plateforme de la bibliothèque math bizarreries, 169**0.5 sortir à, disons, 13.000000000001 ou à 12.99999999999 au lieu de exactement 13.0. À l'aide de round() au lieu de int() gardes contre qui (int(12.99999999) serait de retour le 12, pas le 13 nécessaire ici).

OriginalL'auteur Tim Peters
9

L'original de l'affiche et de l'autre solution posté ici faire la même erreur; si vous utilisez l'opérateur modulo, ou de la division dans n'importe quelle forme, votre algorithme de division de première instance, pas le Crible d'Eratosthène, et sera beaucoup plus lent, O(n^2) au lieu de O(n log log n). Voici un simple Crible d'Eratosthène en Python:
```
def primes(n): # sieve of eratosthenes
ps, sieve = [], [True] * (n + 1)
for p in range(2, n + 1):
if sieve[p]:
ps.append(p)
for i in range(p * p, n + 1, p):
sieve[i] = False
return ps
```
Qui devrait trouver tous les nombres premiers, moins d'un million en moins d'une seconde. Si vous êtes intéressé par la programmation par les nombres premiers, j'ai modestement recommander ce essai à mon blog.

tu veux dire comme ça?????? pastebin.com/ic3ufFZJ
quand j'ai ajouter votre code comme c'est la j'obtiens l'erreur nameerror is_prime pas défini
Pouvez vous s'il vous plaît mettre à jour dans mes codes affichée. Je ne suis pas en mesure de comprendre comment le faire.
Je pense que cela peut être optimisé en ignorant même les numéros de ...

OriginalL'auteur user448810
1

Plus rapide de mise en œuvre de ce que je pouvais penser de
```
def sieve(maxNum):
yield 2
D, q = {}, 3
while q <= maxNum:
p = D.pop(q, 0)
if p:
x = q + p
while x in D: x += p
D[x] = p
else:
yield q
D[q*q] = 2*q
q += 2
raise StopIteration
```
Source: http://code.activestate.com/recipes/117119-sieve-of-eratosthenes/#c4

Remplacer cette partie
```
import math
def is_prime(n):
if n == 2:
return True
if n%2 == 0 or n <= 1:
return False
sqr = int(math.sqrt(n)) + 1
for divisor in range(3, sqr, 2):
if n%divisor == 0:
return False
return True
```
avec
```
primes = [prime for prime in sieve(10000000)]
def is_prime(n):
return n in primes
```
Au lieu de 10000000 vous pouvez mettre tout ce que le nombre maximum jusqu'à laquelle vous avez besoin de nombres premiers.

Comment je l'ai mis dans ce code?? u peut dire comment j'applique cela dans le code ci-dessus? Sera très utile
Veuillez vérifier mes mises à jour de réponse.
Il est devenu plus lent 🙁
Qu'avez-vous donner au lieu de 10000000?
je l'ai fait comme ceci pastebin.com/ic3ufFZJ est-il de droite???

OriginalL'auteur thefourtheye

Voici un très rapide de générateur avec une utilisation réduite de la mémoire.

def pgen(maxnum): # Sieve of Eratosthenes generator
yield 2
np_f = {}
for q in xrange(3, maxnum + 1, 2):
f = np_f.pop(q, None)
if f:
while f != np_f.setdefault(q+f, f):
q += f
else:
yield q
np = q*q
if np < maxnum:  # does not add to dict beyond maxnum
np_f[np] = q+q
def is_prime(n):
return n in pgen(n)
>>> is_prime(541)
True
>>> is_prime(539)
False
>>> 83 in pgen(100)
True
>>> list(pgen(100)) # List prime numbers less than or equal to 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]

OriginalL'auteur dansalmo

Ici est un simple générateur en utilisant uniquement des additions qui ne fait pas de pré-allouer de la mémoire. Le tamis est seulement aussi grand que le dictionnaire des nombres premiers et l'utilisation de la mémoire se développe uniquement en cas de besoin.

def pgen(maxnum): # Sieve of Eratosthenes generator
pnext, ps = 2, {}
while pnext <= maxnum:
for p in ps:
while ps[p] < pnext:
ps[p] += p
if ps[p] == pnext:
break
else:
ps[pnext] = pnext
yield pnext
pnext += 1
def is_prime(n):
return n in pgen(n)
>>> is_prime(117)
>>> is_prime(117)
False
>>> 83 in pgen(83)
True
>>> list(pgen(100)) # List prime numbers less than or equal to 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]

OriginalL'auteur dansalmo

C'est une solution simple avec des ensembles.
Ce qui est très rapide en comparaison avec de nombreux de la liste des algorithmes.
Calcul avec des ensembles est beaucoup plus rapide en raison de la tables de hachage.
(Ce qui rend les jeux plus vite que les listes en python?)

Salutations

----------------------------------
from math import *
def sievePrimes(n):
numbers = set()
numbers2 = set()
bound = round(sqrt(n))
for a in range(2, n+1):
numbers.add(a)
for i in range(2, n):
for b in range(1, bound):
if (i*(b+1)) in numbers2:
continue
numbers2.add(i*(b+1))
numbers = numbers - numbers2
print(sorted(numbers))

La Solution La Plus Simple

OriginalL'auteur AComputerScientist

Vous devez vous connecter pour publier un commentaire.