Proyecto EULER # 35 - La solución Circular Primes es lenta -- python campo con performance campo con programming-challenge campo con python-2.x campo con sieve-of-eratosthenes camp codereview Relacionados El problema

Project Euler #35 - Circular primes solution is slow


7
vote

problema

Español

Este es mi código para Project Euler # 35 (en Python):

El número, 197, se denomina Prime Circular porque todas las rotaciones de los dígitos: 197, 971 y 719, son primordiales.

Hay trece primos de este tipo 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79 y 97.

¿Cuántos primos circulares hay por debajo de un millón?

El programa tarda aproximadamente 2 minutos en correr, y realmente no sé cómo mejorar la eficiencia de ella. Estoy usando un tamiz para generar los primos, y solo estoy revisando las rotaciones hasta que la rotación no sea prima.

  def primes_sieve(limit):     limitn = limit+1     not_prime = [False] * limitn     primes = []      for i in range(2, limitn):         if not_prime[i]:             continue         for f in range(i*2, limitn, i):             not_prime[f] = True          primes.append(i)      return primes  primes = set(primes_sieve(1000000)); exclude = ['2','4','5','6','8','0'] def circularPrime(n):     ss = str(n);     for i in range(n):         if ss[-1] in exclude:             return 0;         if int(ss) not in primes:             return 0;         ss = ss[-1] + ss[:-1];     return 1;  gg = 0; for num in primes:     gg += circularPrime(num); print gg;   

Cualquier ayuda es muy apreciada.

Original en ingles

This is my code for project euler #35 (in Python):

The number, 197, is called a circular prime because all rotations of the digits: 197, 971, and 719, are themselves prime.

There are thirteen such primes below 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97.

How many circular primes are there below one million?

The program takes about 2 minutes to run, and I don't really know how to improve the efficiency of it. I'm using a sieve to generate the primes, and I'm only checking rotations until the rotation isn't prime.

def primes_sieve(limit):     limitn = limit+1     not_prime = [False] * limitn     primes = []      for i in range(2, limitn):         if not_prime[i]:             continue         for f in range(i*2, limitn, i):             not_prime[f] = True          primes.append(i)      return primes  primes = set(primes_sieve(1000000)); exclude = ['2','4','5','6','8','0'] def circularPrime(n):     ss = str(n);     for i in range(n):         if ss[-1] in exclude:             return 0;         if int(ss) not in primes:             return 0;         ss = ss[-1] + ss[:-1];     return 1;  gg = 0; for num in primes:     gg += circularPrime(num); print gg; 

Any help is greatly appreciated.

              
 
 

Lista de respuestas

5
 
vote

Hay cosas que comentar en su código, y hay cosas que optimizar.

Revisión de estilo

  • Evite el código global entre las funciones : su código es difícil de leer mientras espolvoree el código y las funciones entre sí. Esto también hace que sea más difícil reutilizar su código como un módulo, en algún momento en el tiempo.
  • Usa el buen 21 Nombres para variables y funciones - La forma de Pythonic es usar el nombre como 22 o 523 . ¿Y qué es 24 y 25 ? No describen el contenido o el propósito de la variable
  • Las constantes se pueden declarar en la parte superior, usando 26 NOMBRES - Al menos 27 podría ser declarado como una constante. El 28 es un caso de borde, con el que estoy un poco ambivalente. Pero de todos modos, si puedes evitar globals, eso sería lo mejor.
  • 29 TAN STRING, NO LISTA - En su código que usa 50 como una lista de caracteres individuales, y usted hace un 99887766555443331 . El mismo efecto se usa con 52 . Se ve un poco mejor
  • usando 53 en una lista de la lista - en lugar de su bucle usando 54 , usted podría simplemente hacer 99887776655443335 .
  • Cambiar 56 en una función booleana - Creo que es más natural si esta función devolvió 57 o 538 , en lugar de 0 y 1. aún puede resumir todos los valores verdaderos como se indica en el punto de bala anterior
  • Evite los puntos y coma en Python - no necesita los punto y coma, así que quítelos
  • Describa sus funciones - Comentando usando DoCstrings o comentarios ordinarios es bueno cuando los funciones o el fragmento de código se vuelven un poco complicados.

Optimización de código

No me tocaré en la optimización del tamiz, ya que Barry ya ha cubierto eso. Sin embargo, hay algunos puntos que me gustaría hacer de otra manera:

  • En Python 2, es mucho mejor de usar 59 , en lugar de with check: 6.094s w/o check: 6.075s 0 , ya que esta última genera la lista completa en la memoria, mientras que el primero solo define un generador que da Usted el siguiente número cuando lo pides. Especialmente al llegar a números más grandes, esto realmente hace una diferencia
  • Intente evitar los cálculos repetidos o innecesarios - Barry ha tocado esto ya que él discute los límites de usar para los diferentes bucles. Esto se puede ampliar aún más notando que en su caso, si el número contiene los dígitos aún (o 5), una de las rotaciones será una no prima. Usted regresa temprano si encuentra uno, pero también puede construir una gama de solo los candidatos necesarios, y no el bucle sobre todos los primos
  • Similarese su corrección de with check: 6.094s w/o check: 6.075s 1 a with check: 6.094s w/o check: 6.075s 2 , e incluso mejor para 99887776655443343 es una buena captura. Sin embargo, a prueba de estar privilegiada una vez más, ya que cuando llame with check: 6.094s w/o check: 6.075s 4 usted sabe que es un primo. Sin embargo, esto no es extremadamente costoso, ya que es una búsqueda extra en su mesa
  • Otro punto, no verificado en las pruebas de rendimiento, podría ser considerar si sería más rápido construir with check: 6.094s w/o check: 6.075s 5 como una lista de cadenas, ya que su prueba principal contra ella es con cadenas que tiene que convertir de nuevo a un int. Similares, podría ser que el uso de una lista simple en lugar de un conjunto podría valer la pena considerar. Como principio general, es un buen consejo para tratar de evitar muchas converencias entre diferentes tipos.
  • Permita que las funciones devuelvan los valores, y no imprima directamente - Para mejorar la reutilización de las funciones, una función normalmente debe devolver un valor, y no la imprima. Eso es, por supuesto, dado que no es una función de presentación de las clases, en cuyo caso no debe hacer el cálculo en mayor medida.

Aquí hay algún código para probar primos circulares, pruebe solo los posibles candidatos:

  with check:    6.094s w/o check:     6.075s 6  

Esta versión se ejecuta sustancialmente más rápido que su versión. Aquí hay algunas pruebas de sincronización, donde dejé de lado el buidling de la lista principal, y dejé de lado sus versiones cuando tomó mucho tiempo:

  with check:    6.094s w/o check:     6.075s 7  

La versión mod-versión es su código, pero usando with check: 6.094s w/o check: 6.075s 8 . La versión Org es su código, modificado para usar with check: 6.094s w/o check: 6.075s 9 . Y la última es la versión mía. Observe cómo hace el tiempo de mi versión. No crece tan rápido como su versión debido a que no probando todos los números. También tenga en cuenta que probablemente podría ser aún más rápido, si implementé alguna memorización (o similar) para evitar volver a intentar si todas las rotaciones son números primeros. Este efecto aumentaría más dígitos en los candidatos.

 

There are things to comment upon in your code, and there are things to optimize.

Style review

  • Avoid global code in between functions xe2x80x93xc2xa0Your code is hard to read as you sprinkle code and functions in between each other. This also makes it harder to reuse your code as a module, at some point in the time.
  • Use good snake_case names for variables and functions xe2x80x93xc2xa0The pythonic way is to use name like circular_prime or limit_n. And what is ss and gg? They don't describe the content or purpose of the variable
  • Constants can be declared at top, using SNAKE_CASE names xe2x80x93xc2xa0At least excludes could be declared as a constant. The primes is an edge case, which I'm a little ambivalent about. But anyway if you can avoid globals, that would be the best.
  • exclude as string, not list xe2x80x93 In your code you use exclude as a list of single characters, and you do a ss[-1] in exclude. The same effect an be used with exclude = '245680'. It looks a little nicer
  • Using sum() on a list comprehension xe2x80x93 Instead of your loop using gg, you could simply do gg = sum(circularPrime(num) for num in primes).
  • Change circularPrime() into a boolean function xe2x80x93xc2xa0I think it's more natural if this function returned True or False, instead of 0 and 1. You could still sum up all the true values as indicated in previous bullet point
  • Avoid semicolons in Python xe2x80x93xc2xa0You don't need the semicolons, so strip them away
  • Describe your functions xe2x80x93xc2xa0Commenting using docstrings or ordinary comments is good when the functions or code snippet becomes a little complicated.

Code optimisation

I'll not touch in on the sieve optimisation, as Barry has covered that already. However there are a few points I would like to make otherwise:

  • In Python 2 you are much better of using xrange(), rather than range() as the latter generates the entire list in memory, whilst the first only defines a generator which gives you the next number when you ask for it. Especially when getting to larger numbers, this really makes a difference
  • Try avoid repeated or unneccessary calculations xe2x80x93 Barry has touched in on this already as he discusses the limits to use for the different loops. This can further be extended by noting that in your case if the number contains the even digits (or 5), one of the rotations will be a non-prime. You do return early if you find one, but you could also build a range of only the needed candidates, and not loop over all primes
  • Similarily your correction from range(n) to range(len(ss)), and even better to xrange(len(ss)) is a good catch. You do however test for being prime one time extra as when you call circularPrime you know it is a prime. However this is not extremely costly as it one extra lookup in your table
  • Another point, not verified in performance testings, could be to consider whether it would be faster to build primes as a list of strings, since your primary test against it is with strings which you has to convert back to an int. Similarily, it could be that using a plain list instead of a set could be worth considering. As a general principle it good advice to try to avoid to many convertions between different types.
  • Let functions return values, and don't print directly xe2x80x93 To enhance reuse of functions, a function should normally return a value, and not print it out. That is of course given that it is not a presentation function of sorts, in which case it shouldn't do calculation in a greater extent.

Here is some code to test for circular primes, testing only possible candidates:

def all_digit_combinations(allowed_digits, maximum):     """Yield all combinations of allowed_digits below maximum.      For allowed_digits being a list of single digits, i.e. [1, 3, 7, 9],     combine all variants of these digits until we pass the maximum value.     """      no_of_digits = 1      while True:         for digit_tuple in itertools.product(allowed_digits, repeat=no_of_digits):             new_number = reduce(lambda rst, d: rst * 10 + d, digit_tuple)             if new_number < maximum:                 yield new_number             else:                 raise StopIteration          no_of_digits += 1   def is_circular_prime(n):     """Verifies that n and all rotations are prime numbers."""      def are_rotations_prime(n):          ss = str(n);         for i in xrange(len(ss)):             if int(ss) not in PRIMES:                 return False;             ss = ss[-1] + ss[:-1];          return True      return are_rotations_prime(n)   def count_circular_primes_holroy(n):     """Count all circular primes lower than n.      A circular primes is a number which in all rotations of digits are     still prime numbers. That is, 197 is a circular primes at both 197,     971, and 719 are all primes. However 271, is not a circular prime,     since 712 are non-prime, even though 271 and 127 are prime numbers.      With exception of 2 and 5, all circular primes does indeed only     consist of the numbers 1, 3, 7, and 9.      """      # Initialise count, remembering that 2 and 5 are circular primes     count = 2 if n > 5 else 1 if n > 2 else 0      return sum(is_circular_prime(n)                    for n in all_digit_combinations([1, 3, 7, 9], n)) + count   if __name__ == '__main__':     n = 1000000     PRIMES = primes_sieve(n)      print('Count of circular primes below {}: {}'.format(n, count_circular_primes(n))) 

This version runs substantially faster than your version. Here are some timing tests, where I left out the buidling of prime list, and left out your versions when it took to long:

count_circular_primes_org = 100 in   0.001 ms count_circular_primes_mod = 100 in   0.000 ms count_circular_primes_holroy = 100 in   0.000 ms  count_circular_primes_org = 1000 in   0.022 ms count_circular_primes_mod = 1000 in   0.001 ms count_circular_primes_holroy = 1000 in   0.001 ms  count_circular_primes_org = 10000 in   0.951 ms count_circular_primes_mod = 10000 in   0.030 ms count_circular_primes_holroy = 10000 in   0.012 ms  count_circular_primes_mod = 100000 in   2.098 ms count_circular_primes_holroy = 100000 in   0.358 ms  count_circular_primes_holroy = 1000000 in  21.666 ms 

The mod-version is your code, but using xrange(len(ss)). The org-version is your code, modified to use xrange(n). And the last one is mine version. Notice how the time of my version doesn't grow as fast as your version due to not testing each and every number. Also do note that it could probably be even faster, if I implemented some memoisation (or similar) to avoid retesting whether all rotations are prime numbers. This effect would increase the more digits in the candidates there are.

 
 
7
 
vote
vote
La mejor respuesta
 

error

Su programa proporciona la respuesta incorrecta, produciendo 53 en lugar de 55. La razón de esto es que está exagerando ansiosamente las rotaciones en circularPrime si algo termina en un dígito uniforme o 9988777655544331 . Pero 2 y 5 son Prime, ¡pero termina en un dígito que excluye!

Resulta que la verificación de exclusión (además de darle la respuesta incorrecta) en realidad no lo ayuda. Tiempo de su función Ejecutar diez veces:

  with check:    6.094s w/o check:     6.075s   

así que lo deje, y obtiene la respuesta correcta, y se ejecuta más rápido (o lo mismo, dentro del ruido).

Semicolones

Semicolones son un C / C ++ / Java / etc. cosa. Si bien son técnicamente correctan la sintaxis de Python, no los necesitas, y se ven raros, por lo que simplemente puedes soltarlos.

tamiz

Típicamente, iniciaríamos nuestro tamiz con algo así como is_prime = [True] * limitn . Es un poco raro verlo hacia atrás, pero supongo que está bien.

tamizado más eficiente

Echemos un vistazo a la parte del tamiz de su código, intercambiando BOOLS como si sugerí:

  for i in range(2, limitn):     if not is_prime[i]:         continue     for f in range(i*2, limitn, i):         is_prime[f] = False      primes.append(i)   

En primer lugar, tener el continue hace que sea más difícil de leer, mejor para mantener el flujo mono-direccional:

  for i in range(2, limitn):     if is_prime[i]:         primes.append(i)         for f in range(i*2, limitn, i):             is_prime[f] = False   

Ahora, hay dos problemas aquí. En Python 2.7, range() te da una lista. La lista completa . Eso es enormemente unido, ya que nunca desea la lista completa, solo el siguiente elemento uno a la vez. Para eso, hay 50 . Simplemente intercambiando esas dos funciones:

  51  

Ahora, echemos un vistazo a su bucle interno:

  52  

53 es un mal nombre de variable para esto, prefiere algo como 54 , pero eso no es importante. Considerar los límites. En este punto, sabemos que $ I $ es Prime. También sabemos que esta es la primera vez que lo hemos llegado, por lo que cada múltiplo de $ i $ todavía está marcado como potencialmente primo, excepto aquellos divisibles por algún otro Prime $ P & LT; i $. SO $ 2i $ que ya sabemos que no es primo, porque es divisible por $ 2 $. $ 3i £ también. Y así. El primer número compuesto que tenemos que transferirnos será el primero que no sea divisible por cualquier primo $ P $ ... que es $ i ^ 2 $.

  55  

que nos mejora a:

  56  

trae el error

Me encantan los encabezados deliberadamente provocativos. De todos modos, tuvo la idea correcta de verificar los dígitos, pero podemos ser más agresivos con él. Antes de verificar alguna de las rotaciones, verifiquemos la presencia de cualquiera de esos dígitos primero:

  57  

De esta manera, podemos evitar un montón de trabajo para todos nuestros primos de 6 dígitos que comienzan con un número par. Sin embargo, desde lo primero que escribí, sabemos que esto nos dará la respuesta incorrecta. Sin embargo, , sabemos cómo solucionarlo. Sabemos que estamos excluyendo erróneamente 2 y 5, así que vamos a agregarlos de vuelta:

  58  

que nos reduce a:

  59  

Originalmente había dicho que su cheque no le otorgó ningún beneficio de rendimiento, pero esto lo hace, ya que la construcción de todas las rotaciones de cadenas y haciendo todo el 20 es caro y de esta manera nosotros 'Reapre de evitar todo eso arriba. Dado que el número de primos circulares es escaso (¡solo 55 fuera de ~ 75k primos!), Cualquier cosa que podamos hacer para la maleza agresiva que nuestro sistema es bueno.

 

BUG

Your program gives the wrong answer, yielding 53 instead of 55. The reason for this is you over-eagerly exclude rotations in circularPrime if anything ends in an even digit or 5. But 2 and 5 are prime, yet end in a digit that you exclude!

It turns out that the exclusion check (in addition to giving you the wrong answer) doesn't actually help you anyway. Timing your function run ten times:

with check:    6.094s w/o check:     6.075s 

So drop it, and you get the correct answer, and it runs faster (or the same, within noise).

Semicolons

Semicolons are a C/C++/Java/etc. thing. While they're technically correct Python syntax, you don't need them, and they look weird, so you can simply drop them.

Sieve

Typically, we'd start our sieve with something like is_prime = [True] * limitn. It's a little weird to see it backwards, but I guess that's ok.

More efficient sieving

Let's take a look at the sieve part of your code, swapping bools like I suggested:

for i in range(2, limitn):     if not is_prime[i]:         continue     for f in range(i*2, limitn, i):         is_prime[f] = False      primes.append(i) 

First of all, having the continue makes it harder to read - better to keep the flow mono-directional:

for i in range(2, limitn):     if is_prime[i]:         primes.append(i)         for f in range(i*2, limitn, i):             is_prime[f] = False 

Now, there's two issues here. In Python 2.7, range() gives you a list. The full list. That's hugely wasteful since you never want the full list, only the next element one at a time. For that, there's xrange(). Just swapping out those two functions:

range()    6.075s xrange()   4.913s 

Now, let's take a look at your inner loop:

for f in xrange(i*2, limitn, i):     is_prime[f] = False 

f is a bad variable name for this, prefer something like j, but that's not important. Consider the bounds. At this point, we know that \$i\$ is prime. We also know that this is the first time we've gotten to it, so every multiple of \$i\$ is still marked as being potentially prime, except for those divisible by some other prime \$p < i\$. So \$2i\$ we already know isn't prime, because it's divisible by \$2\$. \$3i\$ likewise. And so on. The first composite number that we have to cross off will be the first one not divisible by any such prime \$p\$... which is \$i^2\$.

for j in xrange(i*i, limitn, i):     is_prime[j] = False 

That improves us to:

OP, w/ bugfix         6.075s range() -> xrange()   4.913s inner loop from i^2   4.343s 

Bring back the bug

I love deliberately provocative headings. Anyway, you had the right idea of checking for the even digits, but we can be more aggressive with it. Before we check any of the rotations, let's check for the presence of any of those digits first:

def circularPrime(n):     ss = str(n)     if any(c in ss for c in '024568'):         return 0      # now check everything else 

This way, we can avoid a whole bunch of work for all of our 6-digit primes that start with an even number. However, from the very first thing I wrote, we know that this will give us the wrong answer. However, we know how to fix it. We know we are erroneously excluding 2 and 5, so let's just add them back:

gg = 2 # because 2,5 for num in primes:     gg += circularPrime(num) return gg 

That drops us down to:

OP, w/ bugfix         6.075s range() -> xrange()   4.913s inner loop from i^2   4.343s excluding again       3.721s 

I had originally said your check didn't give you any performance benefit, but this one does - since building up all the string rotations and doing all the int casting is expensive and in this way we're able to avoid all of that up front. Since the number of circular primes is sparse (only 55 out of ~75k primes!), anything we can do to aggressively weed our set down is good.

 
 
3
 
vote

soy un poco estúpido. Esto:

  is_prime = [True] * limitn0  

necesita ser esto:

  is_prime = [True] * limitn1  

Estoy ejecutando innecesariamente las iteraciones en el bucle. El código ahora se ejecuta en 2 segundos en lugar de 2 minutos.

 

I'm kinda stupid. This:

def circularPrime(n):     ss = str(n);     for i in range(n):         if ss[-1] in exclude:             return 0;         if int(ss) not in primes:             return 0;         ss = ss[-1] + ss[:-1];     return 1; 

Needs to be this:

def circularPrime(n):     ss = str(n);     for i in range(len(ss)):         if ss[-1] in exclude:             return 0;         if int(ss) not in primes:             return 0;         ss = ss[-1] + ss[:-1];     return 1; 

I'm unnecessarily running iterations in the loop. The code now runs in 2 seconds instead of 2 minutes.

 
 
     
     
1
 
vote

Aquí está otra forma: use IterTools.Product a Generale todos los candidatos posibles usando dígitos 1,3,7,9 con longitud del número de 1 a 6. Luego, compruebe si todas las rotaciones de los candidatos son primordiales. Si lo son, agregue eso para responder, si no, continúe con el próximo candidato.

Para evitar calcular duplicados, ya que podríamos tener una rotación de otro número en los candidatos, también usamos un diccionario usado para verificar si hemos visto cualquiera de las rotaciones del número que estamos a punto de comprobar.

Como identificador, usé el número máximo de las rotaciones posibles, pero también podría ser MIN. Aquí está el código con esta versión:

  import math import itertools    def get_rotations(num): # returns rotations of a number     string_num = str(num)     arr=[]     for i in range(len(string_num)):         arr.append(int(string_num[i:] + string_num[0:i]))     return arr  def isPrime(n): # we do not check a lot of numbers, so sieve might not be worth it     if n == 1 or n % 2 == 0:         return False      x=3      while(x*x <= n):         if n % x == 0:             return False         x+=2;      return True   answer = 2 # 2 and 5  used = {}  for x in range(1,7):     candidates = set([int(''.join(map(str,uni))) for uni in itertools.product([1,3,7,9], repeat=x)])     for candidate in candidates:         rotations = set(get_rotations(candidate))          st = max(rotations)         if st not in used:             used[st] = True             isCircular = True # we assume its a circular prime             counter = 0;             for x in rotations:                 if not isPrime(x):                     isCircular = False                     break;             if isCircular: # if it was a circular Prime, add to answer the unique permutations                 answer+=len(rotations)         print answer   
 

Here is another way: use itertools.product to generale all possible candidates using digits 1,3,7,9 with number length from 1 to 6. Then check if all the rotations of the candidates are prime. If they are, add that to answer, if not, continue with next candidate.

To prevent calculating duplicates as we might have a rotation of another number in candidates, we also use a used dictionary to check if we have seen any of the rotations of the number we are about to check.

As an identifier, I used the max number of the possible rotations, but could be min as well. Here is the code with this version:

import math import itertools    def get_rotations(num): # returns rotations of a number     string_num = str(num)     arr=[]     for i in range(len(string_num)):         arr.append(int(string_num[i:] + string_num[0:i]))     return arr  def isPrime(n): # we do not check a lot of numbers, so sieve might not be worth it     if n == 1 or n % 2 == 0:         return False      x=3      while(x*x <= n):         if n % x == 0:             return False         x+=2;      return True   answer = 2 # 2 and 5  used = {}  for x in range(1,7):     candidates = set([int(''.join(map(str,uni))) for uni in itertools.product([1,3,7,9], repeat=x)])     for candidate in candidates:         rotations = set(get_rotations(candidate))          st = max(rotations)         if st not in used:             used[st] = True             isCircular = True # we assume its a circular prime             counter = 0;             for x in rotations:                 if not isPrime(x):                     isCircular = False                     break;             if isCircular: # if it was a circular Prime, add to answer the unique permutations                 answer+=len(rotations)         print answer 
 
 
   
   
0
 
vote

Esto debería ser un poco más rápido: UPP: Las permutaciones no funcionarán aquí, pero podemos hacer una función de ciclo encantador

  def cycle(str_num):     return [str_num[i:]+str_num[:i] for i in range(len(str_num))] def circularPrime(n):     ss = str(n);     if any(i in exlude for i in ss): return 0     return all(int(i) in primes for i in cycle(ss))   

Hace un bucle extra, pero es de tamaño fijo, y no debe tomar mucho tiempo comparando el bucle que iba a través de las permutaciones. Pero se sabe que las permutaciones funcionan más rápido de lo habitual para los bucles ( explicación < / a>).

Otra cosa que debe hacer es eliminar primes = set(...) A medida que su generador toma cada primo solo una vez (y la creación de una lista es bastante cara)

También hay una cosa más para sujetar: verificando si una permutación es Prime. Utilicemos el hecho de que solo usamos la función de generación de primera una vez, y el hecho de que acceder a un elemento de la lista por índice es O (1) mientras se comprueba x in list es O (LEN (LISTE))

  limit = 1000000+1 #I inverted this list, but it doesn't make much difference is_prime = [True] * limit primes = []  for i in range(2, limit):     if not is_prime[i]:         continue     for f in range(i*2, limit, i):         is_prime[f] = False      primes.append(i)  evens = ['2','4','5','6','8','0']  # just an option, not sure which is faster, we can make cycle function to be generator def cycle(str_num):     for i in range(len(str_num)):         yield str_num[i:]+str_num[:i]  def is_circular(n):     str_number = str(n)     #I've added a check here, because otherwise 2 isn't counted (contains '2')     if n == 2: return True     if any(i in evens for i in str_number): return False     return all(is_prime[int(i)] for i in cycle(str_number))  count = 0 for num in primes:     count += 1 if is_circular(num) else 0 print count   

Tenga en cuenta que también nombrar correcciones que hice (los nombres claros son mejores que los cortos), y recuerde: no necesitamos punto y coma en Python.

 

This should be a bit faster: UPD: permutations won't work here, but we can make a lovely cycle function

def cycle(str_num):     return [str_num[i:]+str_num[:i] for i in range(len(str_num))] def circularPrime(n):     ss = str(n);     if any(i in exlude for i in ss): return 0     return all(int(i) in primes for i in cycle(ss)) 

It makes one extra loop, but it's fixed-size, and shouldn't take much time comparing to the loop iterating through permutations. But it is known that permutations work faster than usual for-loops (explanation).

Another thing to do is to remove primes = set(...) as your generator takes each prime only once (and making set out of a list is pretty expensive)

Also there is one more thing to fasten: checking if a permutation is prime. Let's use the fact that we only use prime generating function once, and the fact that accessing a list element by index is O(1) while checking x in list is O(len(list))

limit = 1000000+1 #I inverted this list, but it doesn't make much difference is_prime = [True] * limit primes = []  for i in range(2, limit):     if not is_prime[i]:         continue     for f in range(i*2, limit, i):         is_prime[f] = False      primes.append(i)  evens = ['2','4','5','6','8','0']  # just an option, not sure which is faster, we can make cycle function to be generator def cycle(str_num):     for i in range(len(str_num)):         yield str_num[i:]+str_num[:i]  def is_circular(n):     str_number = str(n)     #I've added a check here, because otherwise 2 isn't counted (contains '2')     if n == 2: return True     if any(i in evens for i in str_number): return False     return all(is_prime[int(i)] for i in cycle(str_number))  count = 0 for num in primes:     count += 1 if is_circular(num) else 0 print count 

Please note also naming fixes I made (clear names are better than short ones), and remember: we don't need semicolons in Python.

 
 
     
     

Relacionados problema

16  Eratóstenes Sieve y MPI  ( Eratosthenes sieve and mpi ) 
Escribí esto tamiz de eratóstenes con MPI, pero no estoy seguro de si es bueno suficiente. ¿Debo usar MPI_Scatter y MPI_Gather en lugar de recopilar mat...

5  Reducir el consumo de memoria del tamiz principal 2  ( Reduce prime sieve memory consumption 2 ) 
He hecho un generador de números primarios (para Project Euler). Utiliza el tamiz de Euler (un tamiz modificado de eratóstenes), con un paso de modas. Me gust...

6  Tamiz puramente funcional de eratóstenes  ( Purely functional sieve of eratosthenes ) 
Muchas implementaciones de tamiz de eratóstenes (usados ​​para encontrar números primos hasta un N) Use una matriz mutable temporal para realizar un seguimien...

4  Sieving para números primos  ( Sieving for prime numbers ) 
Quería implementar el tamiz de Erathósthenes hasta int.MaxValue en C #. No se permite que el objeto exceda de 2 GB para que no pueda asignar una matriz 998...

2  Simple tamiz de eratóstenes en Python 3  ( Simple sieve of eratosthenes in python 3 ) 
Otro tamiz de eratóstenes en Python 3. La función devuelve una lista de todos los primos más pequeños pero no iguales max_n . La motivación es, como una ...

8  Encontrar números primos bajo n  ( Find prime numbers under n ) 
Estoy usando el tamiz de Eratóstenes para encontrar números de primos bajo N. ¿Hay algún problema de rendimiento que ve con mi enfoque? Utilicé el LinkedList...

3  Tamiz de eratóstenes: hacerlo más rápido  ( Sieve of eratosthenes making it quicker ) 
Estaba pensando en hacerlo problema 23 del Proyecto Euler. Incluye la dificultad en la que tienes que factorizar a los primos. Ya había hecho eso en problem...

28  Tamiz de eratóstenes - Python  ( Sieve of eratosthenes python ) 
He estado haciendo un montón de Project Euler últimamente y solo quería asegurarme de que mi implementación fuera tan buena como podría ser. ¿Alguien tiene al...

8  Tamiz de eratóstenes en C # con linq  ( Sieve of eratosthenes in c with linq ) 
¿Puede alguien mirar por encima de este tamiz de eratóstenes implementación? Parece casi demasiado fácil. En lugar de mantener un 99887766655544334 ps...

5  Números psicosicos y ordinarios  ( Psycho and ordinary numbers ) 
La declaración del problema se puede encontrar aquí . En resumen, aquí es cuál es el problema sobre: ​​ Se le da un conjunto de números y necesita encontra...




© 2022 respuesta.top Reservados todos los derechos. Centro de preguntas y respuestas reservados todos los derechos