Proyecto EULER + # 35 - Primeros Circulares Summing Menos de N -- python campo con programming-challenge campo con python-3.x campo con primes camp codereview Relacionados El problema

Project Euler+ #35 - Summing circular primes less than N


8
vote

problema

Español

Descripción general

El siguiente código es una solución para una Proyecto Euler + problema en Hackerrank . Una Circular Prime es un número primo cuyas rotaciones también son primordiales. Por ejemplo, 197 es un primo circular ya que y todas las rotaciones (197, 971, 719) son prime.

La suma de todos los primos circulares menos de 100 es:

  sum(2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, 97) = 446    

redability

Después de aprender sobre las explicaciones de la lista en Python, le preocupa que mi legibilidad de código haya tomado una pinza. Me gustaría hacer mi código lo más comprensible posible para que alguien que le establezca pueda deducir rápidamente la estrategia que solía resolver el problema.

En su mayoría, estoy preocupado por mi función generate_circular_primes_less_than a medida que va a 5 bloques anidados profundamente y parece ser más confuso de lo que podría ser.


Aquí está el código para mi solución:

  from math import sqrt, ceil from functools import reduce  # generates a list of n booleans where indexes correspond to primality def prime_sieve(n):     N = [True] * n     N[0] = False     N[1] = False     for i in range(2, int(ceil(sqrt(n)))):         if N[i]:             for j in range(i*2, n, i):                 N[j] = False     return N  # rotates the first i chars of a string to the end def rotate(s, i):     return s[i:] + s[:i]  def generate_circular_primes_less_than(n):     large = 10**len(str(n))     is_prime = prime_sieve(large)      for num in range(n):         if is_prime[num]:             s = str(num)              rotations = [int(rotate(s, i)) for i in range(len(s))]              if reduce(lambda y, x: y and is_prime[x], rotations, True):                 for circular_prime in (r for r in rotations if r < n and is_prime[r]):                     is_prime[circular_prime] = False # remove duplicates (like 11)                     yield circular_prime             else:                 for r in rotations:                     is_prime[r] = False # no need to recheck non-circular primes  # # MAIN if __name__ == "__main__":     n = int(input())     print(sum(generate_all_circular_primes_less_than(n)))   

Sin embargo, el pseudocode que escribí al diseñar mi solución es mucho más simple:

  1. sieve all primes less than the maximum rotation value 2. get the rotations for each prime less than n      if all rotations are prime:        add the rotations less than n to the sum   

A veces, se costuras que agregar comentarios solo enmascaran el código unintitante (como poner lápiz labial en un cerdo). ¿Qué sugerirías mejorar la legibilidad?

Original en ingles

Overview

The following code is a solution for a Project Euler+ problem on Hackerrank. A circular prime is a prime number whose rotations are also prime. For example, 197 is a circular prime since it and all it's rotations (197, 971, 719) are prime.

The sum of all circular primes less than 100 is:

sum(2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, 97) = 446  

Code Redability

After learning about list comprehensions in python, I'm concerned that my code readability may have taken a nosedive. I'd like to make my code as understandable as possible so that someone reading it could quickly deduce the strategy I used to solve the problem.

I'm mostly concerned with my generate_circular_primes_less_than function as it goes 5 nested blocks deep and seems to be more confusing than it could be.


Here's the code for my solution:

from math import sqrt, ceil from functools import reduce  # generates a list of n booleans where indexes correspond to primality def prime_sieve(n):     N = [True] * n     N[0] = False     N[1] = False     for i in range(2, int(ceil(sqrt(n)))):         if N[i]:             for j in range(i*2, n, i):                 N[j] = False     return N  # rotates the first i chars of a string to the end def rotate(s, i):     return s[i:] + s[:i]  def generate_circular_primes_less_than(n):     large = 10**len(str(n))     is_prime = prime_sieve(large)      for num in range(n):         if is_prime[num]:             s = str(num)              rotations = [int(rotate(s, i)) for i in range(len(s))]              if reduce(lambda y, x: y and is_prime[x], rotations, True):                 for circular_prime in (r for r in rotations if r < n and is_prime[r]):                     is_prime[circular_prime] = False # remove duplicates (like 11)                     yield circular_prime             else:                 for r in rotations:                     is_prime[r] = False # no need to recheck non-circular primes  # # MAIN if __name__ == "__main__":     n = int(input())     print(sum(generate_all_circular_primes_less_than(n))) 

However, the pseudocode I wrote when designing my solution is much simpler:

1. sieve all primes less than the maximum rotation value 2. get the rotations for each prime less than n      if all rotations are prime:        add the rotations less than n to the sum 

Sometimes it seams that adding comments only masks unintuitive code (like putting lipstick on a pig). What would you suggest to improve the readability?

           
     
     

Lista de respuestas

6
 
vote
vote
La mejor respuesta
 

Reemplace la lista de todos los números hasta n con un diccionario de primos solo

Como se representa, 9988776655544331 MANTENIMIENTO PRINCIPANTE False Valores, que nunca se usan. Sería más idiomático usar un diccionario, más el operador 9988776555555443333 , lo que le dice si existe una clave en particular en el diccionario. Como proporción de primos por debajo de un número dado n se aproxima por $ n / mathcal {ln} (n) $, un diccionario que contiene solo primos como las teclas serían más pequeñas que su lista por un Factor de aproximadamente $ N / Mathcal {log} (n) $, mientras que la búsqueda sería tan rápido.

Su principal tamiz se vería así:

  def prime_sieve(n):     '''Your docstring here.     '''     sieve = dict.fromkeys([i for i in range(n)])   # make a dict of all numbers up to n     for i in range(2, ceil(sqrt(n))):         if i in sieve:             for j in range(i**2, n, i):                 del sieve[j]                       # remove composites from dict     return sieve   

(Nota: Incluso con esta modificación, el tamiz aún comienza en el tamaño n , y toma el orden de $ mathcal {o} (n ^ 2) $ Operaciones para generar. Esta es una propiedad fundamental del tamiz de los Erasóstenes. Una implementación más rápida podría renunciar al tamiz, generar candidatos candidatos, y probarlos individualmente, por ejemplo, usando Miller-rabin Prueba de primalidad.)

Siga su propio pseudocode

Dicen en la programación de que el buen código debería leer como la prosa. Lo que significa que debe leer lo más cerca posible de una oración natural. Escribiendo su programa como Pseudocódigo es una excelente manera de priorizar la legibilidad. El Pseudocódigo ya le brinda la versión más legible de su código como un lugar para comenzar. La tarea es luego reescribirla de acuerdo con la sintaxis y los modismos del idioma que elija.

Basado en su propio Pseudocódigo, necesitamos:

  • (1) una forma sencilla de invocar el tamiz. Ya tiene eso con su función prime_sieve .

Aquí, su variable large debe ser algo más descriptivo. Tomando señales de su pseudocódigo, podemos llamarlo max_Rotation.

  max_rotation = 10**len(str(n)) primes = prime_sieve(max_rotation)   

(Nota: Cambié el nombre de la salida de N0 a N1 , como la implementación de nuevo 99887766655443312 contiene solo números primos). < / p>

  • (2) un encabezado de bucle que deja en claro que estamos obteniendo todas las rotaciones de cada primo menos que N3 .

traducido a Python, la segunda línea de su pseudocódigo se convierte en:

  N4 

Esto implica que las operaciones, como la conversión del entero N5 N6 , en lugar de obstruir el cuerpo principal de su función N7 .

Tal función se vería así:

  N8 

(Nota: usando N9 se asegura de que todas las rotaciones devueltas sean únicas).

  • (3) Compruebe si todas las rotaciones resultantes son Prime.

Aquí, es más claro y más idiomático para usar el False0 Expresión incorporada.

  False1  
  • (4) y, finalmente, debemos producir solo aquellos primos circulares que son menores que el 99887766555443322

El código final se ve así:

  False3  

Observe que las últimas cinco líneas coinciden estrechamente con su pseudocódigo (con la excepción de la actualización del conjunto False4 ).


[A continuación se muestra un resumen de las ediciones sugeridas por Eneil .]


Usted usa False5 innecesariamente aquí:

  False6  

Porque False7 Ya devuelve un número entero, enviándolo en False8 es redundante.


La siguiente línea se puede mejorar para omitir múltiplos de primos que ya se han identificado:

  False9  

Como lo tiene, in0 incrementos a través de múltiplos de todos los enteros entre in1 y 2, además de los enteros que estamos interesados, aquellos mayores que in2 . Como múltiplos de todos los enteros a continuación, ya me han eliminado de la lista principal, se pueden omitir en las rondas posteriores. Entonces, J debería iniciarse J ** 2, el primer compuesto que no se ha visto antes. El bucle mejorado se ve así:

  in3  

 

Replace the list of all numbers up to n with a dictionary of primes only

As it stands, N holds mainly False values, which are never used. It would be more idiomatic to use a dictionary, plus Python's in operator, which tells you whether a particular key exists in the dictionary. As the proportion of primes below a given number n is approximated by \$n /\mathcal{ln}(n)\$, a dictionary containing only primes as keys would be smaller than your list by a factor of about \$n/\mathcal{log}(n)\$, while look-up would be just as fast.

Your prime sieve would look like this:

def prime_sieve(n):     '''Your docstring here.     '''     sieve = dict.fromkeys([i for i in range(n)])   # make a dict of all numbers up to n     for i in range(2, ceil(sqrt(n))):         if i in sieve:             for j in range(i**2, n, i):                 del sieve[j]                       # remove composites from dict     return sieve 

(Note: even with this modification, the sieve still begins at size n, and takes on the order of \$\mathcal{O}(n^2)\$ operations to generate. This is a fundamental property of the Sieve of Erasosthenes. A faster implementation might forgo the sieve, generate candidate circular primes, and test them individually, e.g. using Miller-Rabin primality test.)

Follow your own pseudocode

They say in programming that good code should read like prose. Which means it should read as close to a natural sentence as possible. Writing out your program as pseudocode is a great way to prioritize readability. The pseudocode already gives you the most readable version of your code as a place to start. The task is then to rewrite it according to the syntax and idioms of the language you choose.

Based on your own pseudocode, we need:

  • (1) A simple way to invoke the sieve. You have that already with your prime_sieve function.

Here, your variable large should be something more descriptive. Taking cues from your pseudocode, we can call it max_rotation.

max_rotation = 10**len(str(n)) primes = prime_sieve(max_rotation) 

(Note: I changed the name of the output of prime_sieve to primes, as the new dict implementation contains only primes.)

  • (2) A loop header that makes it clear that we are getting all rotations of each prime less than n.

Translated into Python, the second line of your pseudocode becomes:

for rotations in [get_rotations(i) for i in range(n)]: 

This implies that operations such as conversion of the integer i to a string, removal of duplicates, and accumulation into a list, should all be handled by the function rotations, rather than clogging up the main body of your generate_circular_primes function.

Such a function would look like this:

def get_rotations(num)     '''Your docstring here.     '''     def rotate(s, i):         return s[i:] + s[:i]     s = str(num)     return set([int(rotate(s, i)) for i in range(len(s))]) 

(Note: using set() makes sure all rotations returned are unique.)

  • (3) Check if all the resulting rotations are prime.

Here, it's clearest and most idiomatic to use the all() built-in expression.

    if all(r in primes for r in rotations): 
  • (4) And finally, we must yield only those circular primes that are less than the original n.

The final code looks like this:

from math import sqrt, ceil  def prime_sieve(n):     '''Your docstring here.     '''     sieve = dict.fromkeys([i for i in range(n)])     for i in range(2, ceil(sqrt(n))):         if i in sieve:             for j in range(i**2, n, i):                 if j in sieve:                     del sieve[j]     return sieve  def get_rotations(num):     '''Your docstring here.     '''     def rotate(s, i):         return s[i:] + s[:i]     s = str(num)     return set([int(rotate(s, i)) for i in range(len(s))])  def get_circular_primes(n):     '''Your docstring here.     '''     circular = set()     max_rotation = 10**len(str(n))      primes = prime_sieve(max_rotation)     for rotations in [get_rotations(i) for i in range(n)]:         if all((r in primes) for r in rotations):             circular.update(rotations)     yield [c for c in circular if c < n] 

Notice that the last five lines closely match your pseudocode (with the exception of updating the set circular).


[Below is a summary of edits suggested by enedil.]


You use int() unnecessarily here:

    for i in range(2, int(ceil(sqrt(n)))): 

Because ceil() already returns an integer, wrapping it in int() is redundant.


The following line can be improved to skip multiples of primes that have already been identified:

        for j in range(i*2, n, i): 

As you have it, j increments through multiples of all integers between i and 2, in addition to the integers we are interested in, those greater than i. As multiples of all integers below i have already been removed from the prime list, they can be skipped in subsequent rounds. So, j should be initiated at i**2, the first composite that has not been seen before. The improved loop looks like this:

        for j in range(i**2, n, i): 
 
 
2
 
vote

Hay algunas cosas que puede hacer para mejorar la legibilidad general:

  • Los comentarios que tiene antes de las funciones deben ser las documentos regulares de Python DOCSTRINGS
  • El N Variable en el prime_sieve() no es la mejor opción: en primer lugar, el mayúscula debe usarse para cosas constantes ( REFERENCIA DE PEP8 ) Y, 9988776655544332 no tiene sentido, ¿qué hay de llamar es sieve ?
  • Puede acortar la definición del elemento de tamiz inicial a sieve[0] = sieve[1] = False
  • No se olvide de la Uso adecuado de los espacios blancos en expresiones < / a>

Aquí están las dos primeras funciones que aplican los cambios sugeridos:

  def prime_sieve(n):     """Generates a list of n booleans where indexes correspond to primality."""     sieve = [True] * n     sieve[0] = sieve[1] = False     for i in range(2, int(ceil(sqrt(n)))):         if sieve[i]:             for j in range(i * 2, n, i):                 sieve[j] = False     return sieve   def rotate(s, i):     """Rotates the first i chars of a string to the end."""     return s[i:] + s[:i]   

Ahora, veamos lo que podemos hacer sobre la función 9988776665544336 .

En primer lugar, la función no es fácilmente comprensible y realmente está perdiendo un documento útil y comentarios significativos que explican la forma en que funciona.

También, puede disminuir la anulación negando la primera condición y usando continie Declaración :

  for num in range(n):     if not is_prime[num]:         continue      s = str(num)     # ...   

También definiría el circular_primes como variable separada, reemplazando:

  prime_sieve()0  

con:

  prime_sieve()1  

El prime_sieve()2 también puede beneficiarse de definir con un nombre de variable legible, por ejemplo:

  prime_sieve()3  

FYI, esto se conoce comúnmente como "extracto variable" técnica de refactorización .

 

There are some things you can do to improve overall readability:

  • the comments that you have before the functions should be the regular Python docstrings
  • the N variable in the prime_sieve() is not the best choice - first of all, the upper-case should be used for constant things (PEP8 reference) and, N is meaningless, how about calling it sieve?
  • you can shorten the initial sieve element definition to sieve[0] = sieve[1] = False
  • don't forget about the proper use of white spaces in expressions

Here are the first two functions applying the suggested changes:

def prime_sieve(n):     """Generates a list of n booleans where indexes correspond to primality."""     sieve = [True] * n     sieve[0] = sieve[1] = False     for i in range(2, int(ceil(sqrt(n)))):         if sieve[i]:             for j in range(i * 2, n, i):                 sieve[j] = False     return sieve   def rotate(s, i):     """Rotates the first i chars of a string to the end."""     return s[i:] + s[:i] 

Now, let's see what we can do about the generate_circular_primes_less_than function.

First of all, the function is not easily understandable and is really missing a helpful docstring and meaningful comments explaining the way it works.

Also, you can decrease the nestedness by negating the first condition and using continie statement:

for num in range(n):     if not is_prime[num]:         continue      s = str(num)     # ... 

I would also define the circular_primes as a separate variable, replacing:

for circular_prime in (r for r in rotations if r < n and is_prime[r]):     is_prime[circular_prime] = False # remove duplicates (like 11)     yield circular_prime 

with:

circular_primes = (r for r in rotations if r < n and is_prime[r]) for circular_prime in circular_primes:     is_prime[circular_prime] = False  # remove duplicates (like 11)     yield circular_prime 

The reduce() part can also benefit from defining with a readable variable name, e.g.:

check_circular_primes = reduce(lambda y, x: y and is_prime[x], rotations, True) if check_circular_primes:     # ... 

FYI, this is commonly known as "Extract Variable" refactoring technique.

 
 
2
 
vote

Puede que no sea un experto en la legibilidad del código o ese problema especial dado, pero mi sugerencia sería generalmente acortar la cantidad de texto en su código.

Tal vez prime_sieve()4 fue mejor leer si escribió algo como:

  prime_sieve()5  

No sé si eso lo ayuda, pero tener menos personajes en la pantalla siempre ayudaría a optimizar la legibilidad, y personalmente creo que un nombre de función debería ser corto y directo, la descripción debe ser comentarios.

 

I may not be an expert on code readability or that special given problem, but my suggestion would be to generally shorten the amount of text in your code.

Maybe generate_circular_primes_less_than was better to read if you wrote something like:

#generate circular primes less than var def circPrimes(n):     [ ... ] 

I don't know if that helps you at all, but having less characters on the screen would always help to optimize readability, and I personally think a function name should be short and straight forward, description should be comments.

 
 

Relacionados problema

5  Encuentre el próximo número Prime - Control de flujo de los bucles anidados 'para `  ( Find the next prime number flow control of nested for loops ) 
Este código funciona perfectamente, pero me molesta. Tener un bucle etiquetado y anidado Bucle, con un Enumerable<T>.Empty()0 Declaración, y un 9988777665...

5  La suma de primos toma para siempre  ( Summation of primes takes forever ) 
Project Euler Problema 10 Pregunta: "¿Cuál es la suma de todos los números primeros por debajo de 2 millones?" ¿Cómo aceleré mi código? Está tomando para ...

9  Factorización de números rápidos en Python  ( Fast number factorization in python ) 
Aquí está mi implementación para factorizar un entero positivo: require File.expand_path(File.dirname(__FILE__) + '/edgecase') # Project: Create a Proxy C...

3  Análisis de simetría para arreglos atómicos en un cristal  ( Symmetry analysis for atom arrangements in a crystal ) 
Por un tiempo ahora he tenido la intención de publicar un poco de mi código Haskell aquí para que alguien pueda decirme qué partes de la biblioteca de idiomas...

4  Encontrar y probar la primalidad  ( Finding and testing primality ) 
He escrito una clase que es responsable de ambos primos enumerantes y probando la primalidad de un número. Aquí está el código: public static class Prime...

1  Encuentra el Kth Prime y todos los primos debajo de él  ( Find the kth prime and all the primes below it ) 
Funciona al encontrar 2N + 1 con N de 1 a K, pero no donde 2N + 1 sería divisible por uno de los primos ya conocidos. Me gustaría saber si el programa puede e...

2  Números primos menos que un número dado n  ( Prime numbers less than a given number n ) 
Entonces, empecé este desafío en Codeeeval , que solicita imprimir el número de números primos menos que cualquier entero dado N, donde 0 & lt; N & lt; 4,294...

1  Reto de primos consecutivos en Codeeeval.com  ( Consecutive primes challenge at codeeval com ) 
Estoy trabajando a través de un nuevo desafío en Codeeeval.com y creo que estoy obteniendo un resultado correcto, pero no puedo pasar por su alumnador. No est...

2  Imprimiendo todos los números primeros entre dos límites  ( Printing all the prime numbers between two bounds ) 
Sigo recibiendo un límite de tiempo excedido para esta solución a SPOJ PRIME1 . Necesito imprimir todos los números primos dentro de un intervalo dado (con i...

5  Proyecto EULER # 3 IN C # - Factor principal más grande  ( Project euler 3 in c largest prime factor ) 
Acabo de empezar a hacer los desafíos de Project Euler y en este momento estoy en el desafío # 3: el factor primordial más grande del 600851475143. Escrib...




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