Hola ¿alguien puede decirme cómo implementar la Criba de Eratóstenes en este código para hacerlo rápido? La ayuda será muy agradecido si usted puede completar con tamiz. Realmente estoy teniendo problemas para hacer esto en este código.

#!/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
InformationsquelleAutor user2876096 | 2013-10-13

6 Comentarios

  1. 12

    Un viejo truco para acelerar los tamices en Python es el uso de la fantasía 😉 de la lista de la notación de segmentos, como el de abajo. Este utiliza Python 3. Cambios necesarios para Python 2 se señaló en los comentarios:

    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 devuelve una lista; en Python 3 un iterador. Aquí en Python 3:

    >>> list(sieve(20))
    [2, 3, 5, 7, 11, 13, 17, 19]
    >>> len(list(sieve(1000000)))
    78498

    Los que ambos se ejecutan en un parpadeo. Dado que, he aquí cómo construir un is_prime función:

    primes = set(sieve(the_max_integer_you_care_about))
    def is_prime(n):
    return n in primes

    Es el set() parte que hace que sea rápido. Por supuesto, la función es tan simple que probablemente querría escribir:

    if n in primes:

    directamente en vez de jugar con:

    if is_prime(n):
    • Gracias por la respuesta pero ahora, cuando los números primos son generados. no son en comparación con la suma de los números en la lista así que todo el código es más rápido.
    • el código es más rápido que antes, muchas gracias. Pero la suma de la parte y comparar parte es todavía lento 🙁
    • si necesita más ayuda, creo que se debe abrir una nueva pregunta, mostrando el código exacto que está utilizando ahora. Esto la pregunta era sobre el uso de un tamiz, y ya ha sido contestada 😉
    • gracias yo tengo trabajo. Ahora se resuelve 50000×50000 listas en 7 minutos 🙂 muchas Gracias a todos por la ayuda.
    • Peters Gracias por la excelente respuesta! Para el propósito de este tamiz sqrtn = int(n**0.5) debería ser suficiente, ¿verdad?
    • Yadav, mejor prevenir que curar. Por ejemplo, considere la posibilidad de n=169. La exponenciación se implementa mediante la adopción de un logaritmo de debajo de las mantas, multiplicando por el poder, y luego elevar la base del logaritmo a ese resultado. Dependiendo de la plataforma de matemáticas de la biblioteca peculiaridades, 169**0.5 los salir para, digamos, 13.000000000001 o a 12.99999999999 en lugar de exactamente 13.0. El uso de round() en lugar de int() guardias en contra de que (int(12.99999999) volvería 12, no 13 se necesita aquí).

  2. 9

    Tanto el cartel original y la otra solución, publicado aquí en el mismo error; si utiliza el operador de módulo, o la división en cualquier forma, su algoritmo de prueba de la división, no la Criba de Eratóstenes, y va a ser mucho más lento, O(n^2) en lugar de O(n log log n). Aquí es un simple Criba de Eratóstenes 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

    Que debe encontrar todos los números primos menos de un millón en menos de un segundo. Si usted está interesado en la programación con los números primos, yo modestamente recomendar esta ensayo en mi blog.

    • te refieres a como esta????? pastebin.com/ic3ufFZJ
    • cuando me agregue a su código es el que me dan error nameerror is_prime no definido
    • Puede usted por favor, actualice en mi código publicados. Yo no soy capaz de entender cómo hacerlo.
    • Creo que este puede ser optimizado mediante la omisión de números …
  3. 1

    Más rápido de la aplicación de lo que podía pensar

    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

    Fuente: http://code.activestate.com/recipes/117119-sieve-of-eratosthenes/#c4

    Sustituir esta parte

    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

    con

    primes = [prime for prime in sieve(10000000)]
    def is_prime(n):
    return n in primes

    Lugar de 10000000 usted puede poner cualquiera que sea el número máximo hasta el que necesita de números primos.

    • Cómo lo pongo en este código?? u puede decir cómo puedo aplicar esto en el código anterior? Va a ser muy útil
    • Por favor revise mi respuesta actualizada.
    • Se hizo más lento 🙁
    • ¿Qué te dan en vez de 10000000?
    • yo lo hice como esta pastebin.com/ic3ufFZJ es correcto???
    • fue 1000000 ?
    • No, no es. Me han dado el código para utilizar en lugar de is_prime. El uso que.
    • el sieve algo que mostrar debe ser utilizado en pospuesto variación. Se utiliza mucha menos memoria y se convierte en un poco más rápido.
    • Puede usted por favor, actualice en mi código publicados. Yo no soy capaz de entender es cómo hacerlo…
    • cuando me agregue a su código es el que me dan error nameerror is_prime no definido
    • Apuesto a que el código fue más lento debido a que salió de primes como una lista, de modo n in primes hace un lento búsqueda lineal. Envuélvalo en una set().

  4. 0

    Aquí es muy rápida generador con uso reducido de memoria.

    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]
  5. 0

    Aquí es un simple generador, utilizando solo, además de que no se pre-asignar memoria. El tamiz es sólo tan grande como el diccionario de números primos y el uso de la memoria crece sólo cuando sea necesario.

    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]
  6. 0

    Esta es una solución simple con conjuntos.
    Que es muy rápido en comparación con muchos de la lista de algoritmos.
    Cálculo con los juegos es mucho más rápido porque de las tablas de hash.
    (Lo que hace que los conjuntos más rápido que las listas en python?)

    Saludos

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

    Solución Simple

Dejar respuesta

Please enter your comment!
Please enter your name here