Informática Reto 1 de programación: Generar los primeros x números primos, animate y pon tú solución

[JC Denton]

@Jorge2019 y yo estabamos a punto de medirnos las pollas haciendo un reto de programación y bueno, en vez de ser entre dos pues que sea entre todos los que se animen

En este caso es generar e imprimir los primeros primos contenidos hasta el número 10.000.000 o lo que es lo mismo, los primos que hay entre el 0 y el 10.000.000

El más rápido gana, de momento eso lo dejamos para luego porque cada ordenador es un mundo y ya se verá como se hace

Y bueno, aqui tenemos una implementación a lo bruto, es O(n²) pero hace el trabajo y por lo tanto es mi primera "entrega", muy mejorable pero de eso se trata, de que haya una compentecia para darle emoción al asunto

Rust Playground

A browser interface to the Rust compiler to experiment with the language

play.rust-lang.org

No puede ser más sencillo, literalmente coge un número y prueba a dividir entre todos los demas a partir del 2, si nadie lo divide es que es primo. Solo calcula hasta 100 porque da lo mismo 100 que 10 millones, el algoritmo es el mismo

------------------------------------------------

Trucos para detecar si un número es primo

- En vez de probar desde el 2 hasta n (o el propio número) hay una propiedad matemática que dictamina que solo es necesario probar hasta raiz de n, o lo que es lo mismo, si tengo el número 100 para ver si es primo le hago la raíz que es 10 y solo tendría que probar desde el 2 hasta el 10, me ahorro probar desde el 10 hasta el 99, un ahorro de calculo importante

- Hay otra propiedad llamada teorema fundamental de la aritmética que dice que se pueden encontrar rangos de números entre los que no hay primos, viene a ser k!+2, k! + 3,..., k!+k

! es el factorial, pongo un ejemplo, para k = 6
__ 6!+2 = 722
__ 6!+3 = 723
__ 6!+4 = 724
__ 6!+5 = 725
__ 6!+6 = 726

Con lo que en el rango de [722,726] no hay números primos, si en vez de k = 6 usamos un valor grande el rango será más grande (el rango es de k elementos) y puede ahorrar más tiempo de cálculo porque vamos eliminando opciones

-----------------------------------------------

Pues nada, espero que os animeis

 

[JC Denton]

Con las prisas se me ha olvidado otro truco/mejora

Los números pares nunca van a ser primos, por favor, no hagais el modulo con 2 porque no es eficiente, en vez de eso haced que el bucle principal suba de 2 en 2, es decir, que i (o como lo querais llamar) sea 3, 5, 7, 9,..... En vez de ir sumando uno (1, 2, 3, 4, ....) sumadle 2, serán la mitad de operaciones

 

[Miembro eliminado 6516 Jorge2019]

A correr tol mundo

 

[singermorning]

Funcionaria crear un vector 0:1000000 aplicar de manera vectorizada el calculo del modulo, y seleccionar aquellos cuyo modulo es mayor que cero?

Se me antoja facil si es asi....

 

[Miembro eliminado 6516 Jorge2019]

Ceno y posteo mi script

 

[∆N∅M∆L¥]

Ceno y posteo mi script

Espero para ver el resultado! A mí es que lo único...se me ocurre usar la criba de Eratostenes en Phyton para generar los primos hasta 10,000,000... pero nah, o no tengo yo la cabeza ahora para esto o directamente no llego aún con mis conocimientos.

 

[JC Denton]

Funcionaria crear un vector 0:1000000 aplicar de manera vectorizada el calculo del modulo, y seleccionar aquellos cuyo modulo es mayor que cero?

Se me antoja facil si es asi....

No pero con un ligero cambio podría funcionar

Si empiezo tendría el número 2

- 2mod2 = 0 => Es primo

Los modulos 0 tienen a numeros primos

Y si optase por no hacerme caso y probar con pares (porque es un ejemplo más fácil)

- 16mod5 = 1 => 16 = 8*2 = 2*2*2*2 => Compuesto y no es primo

Como ves si es mayor que cero hay compuestos pero si sigues mirando el caso concreto del 0 ahi si que hay primos

Si necesitas ayuda dilo pero la gracia es que cada uno a su ritmo

 

[JC Denton]

Espero para ver el resultado! A mí es que lo único...se me ocurre usar la criba de Eratostenes en Phyton para generar los primos hasta 10,000,000... pero nah, o no tengo yo la cabeza ahora para esto o directamente no llego aún con mis conocimientos.

Poco a poco, la criba es un mal algoritmo pero es mejor que el que yo he puesto asi que podrías ponerte en cabeza

 

[WEKurtz]

Estas cosas las programaba yo en BASIC en los 80... xDD

 

[Miembro eliminado 6516 Jorge2019]

He probado con varios algoritmos
el que mejor resultado me ha dado ha sido con Eratóstenes

aquí la waina

import numpy as np
import math
from timeit import default_timer as timer

def sieve_of_eratosthenes(limit):
    sieve = np.ones(limit, dtype=bool)
    sieve[:2] = False   # 0 y 1 no son primos
    for num in range(2, int(math.sqrt(limit)) + 1):
        if sieve[num]:
            sieve[num*num::num] = False
    return np.nonzero(sieve)[0]

if __name__ == '__main__':
    LIMIT = 10_000_000

    # Medir el tiempo para calcular los números primos
    start_time_calc = timer()

    primes = sieve_of_eratosthenes(LIMIT)

    end_time_calc = timer()
    calc_execution_time = end_time_calc - start_time_calc

    # Medir el tiempo de impresión
    start_time_print = timer()

    print(f"Números primos entre 0 y {LIMIT}:")
    for prime in primes:
        print(prime)

    end_time_print = timer()
    total_execution_time = end_time_print - start_time_calc
    print_execution_time = end_time_print - start_time_print

    # Resultados
    print(f"Total de numeros primos encontrados: {len(primes)}")
    print(f"Tiempo para calcular los numeros primos: {calc_execution_time} segundos")
    print(f"Tiempo para imprimir los numeros primos: {print_execution_time} segundos")
    print(f"Tiempo total (calculo + impresion): {total_execution_time} segundos")

Total de numeros primos encontrados: 664579
Tiempo para calcular los numeros primos: 0.01990989997284487 segundos
Tiempo para imprimir los numeros primos: 6.470142100006342 segundos
Tiempo total (calculo + impresion): 6.490053399989847 segundos

 

[singermorning]

No pero con un ligero cambio podría funcionar

Si empiezo tendría el número 2

- 2mod2 = 0 => Es primo

Los modulos 0 tienen a numeros primos

Y si optase por no hacerme caso y probar con pares (porque es un ejemplo más fácil)

- 16mod5 = 1 => 16 = 8*2 = 2*2*2*2 => Compuesto y no es primo

Como ves si es mayor que cero hay compuestos pero si sigues mirando el caso concreto del 0 ahi si que hay primos

Si necesitas ayuda dilo pero la gracia es que cada uno a su ritmo

Perdon, mew referia al resto...

 

[JC Denton]

Estas cosas las programaba yo en BASIC en los 80... xDD

Eso eran lenguajes....

Antes de que MS lo jodiera todo con Visual

La verdad es que yo soy demasiado joven y no he llegado a tocarlo

 

[JC Denton]

He probado con varios algoritmos
el que mejor resultado me ha dado ha sido con Eratóstenes

aquí la waina

import numpy as np
import math
from timeit import default_timer as timer

def sieve_of_eratosthenes(limit):
    sieve = np.ones(limit, dtype=bool)
    sieve[:2] = False   # 0 y 1 no son primos
    for num in range(2, int(math.sqrt(limit)) + 1):
        if sieve[num]:
            sieve[num*num::num] = False
    return np.nonzero(sieve)[0]

if __name__ == '__main__':
    LIMIT = 10_000_000

    # Medir el tiempo para calcular los números primos
    start_time_calc = timer()

    primes = sieve_of_eratosthenes(LIMIT)

    end_time_calc = timer()
    calc_execution_time = end_time_calc - start_time_calc

    # Medir el tiempo de impresión
    start_time_print = timer()

    print(f"Números primos entre 0 y {LIMIT}:")
    for prime in primes:
        print(prime)

    end_time_print = timer()
    total_execution_time = end_time_print - start_time_calc
    print_execution_time = end_time_print - start_time_print

    # Resultados
    print(f"Total de numeros primos encontrados: {len(primes)}")
    print(f"Tiempo para calcular los numeros primos: {calc_execution_time} segundos")
    print(f"Tiempo para imprimir los numeros primos: {print_execution_time} segundos")
    print(f"Tiempo total (calculo + impresion): {total_execution_time} segundos")

Total de numeros primos encontrados: 664579
Tiempo para calcular los numeros primos: 0.01990989997284487 segundos
Tiempo para imprimir los numeros primos: 6.470142100006342 segundos
Tiempo total (calculo + impresion): 6.490053399989847 segundos

No esta mal, por lo menos haces la raiz como he dicho aunque no te saltas los números pares que ya sabes de antemano que no van a ser primos

Pero como el cuello de botella lo tienes en el print() te diré un secreto, tarda tanto porque cada print tiene que hacer un .flush o lo que es lo mismo, escribir lo que tenga. Si en vez de hacer prints como un loco cada una de las 664579 veces lo haces sin borrar el buffer a la fuerza el tiempo bajará bastante

Hoy ya no pero mañana lo subiré a una nube de Python (para que los tiempos sean comparables) y te voy a mejorar la parte del algoritmo un poco

 

[Miembro eliminado 6516 Jorge2019]

No esta mal, por lo menos haces la raiz como he dicho aunque no te saltas los números pares que ya sabes de antemano que no van a ser primos

Pero como el cuello de botella lo tienes en el print() te diré un secreto, tarda tanto porque cada print tiene que hacer un .flush o lo que es lo mismo, escribir lo que tenga. Si en vez de hacer prints como un loco cada una de las 664579 veces lo haces sin borrar el buffer a la fuerza el tiempo bajará bastante

Hoy ya no pero mañana lo subiré a una nube de Python (para que los tiempos sean comparables) y te voy a mejorar la parte del algoritmo un poco

estoy deseando ver lo que dises
por cierto
no tengo ni pajolera idea de rust
qué tiempos está dando tu script en tu máquina?

 

[JC Denton]

Perdon, mew referia al resto...

El modulo devuelve el resto

- 3mod2
- 3 % 2

Es lo mismo y ambos van a devolver 1. Antes vimos que hay modulos/restos distintos de 0 que son compuestos asi que creo que no es algo válido, la propiedad importante del módulo/resto es precisamente que sea igual a 0 ya que significa que si que lo divide

No se si eso a lo que te refieres, pon un código aunque no compile por si no es eso no lo entiendo

 

[Zollkron]

Buenas sólo paso a recordaros que el 2 es par y es primo. Lo digo por no tener que darle a nadie un capón por decir que no existe un número primo que sea par. Y con las mismas me cojo y me voy, suerte con ello.

 

[JC Denton]

estoy deseando ver lo que dises
por cierto
no tengo ni pajolera idea de rust
qué tiempos está dando tu script en tu máquina?

Menos de un segundo

Lo acabaré poniendo pero vamos, yo hago un truco

Es pronto pero si, en un par de dias o asi lo subo para que todo el mundo pueda verlo

Uso Rust porque si usase C++ no se enteraba ni el apuntador Pero vamos, es parecido a Python, ya digo que hago lo básico, todos los numeros los pruebo con todos los que tengan por debajo

 

[JC Denton]

Buenas sólo paso a recordaros que el 2 es par y es primo. Lo digo por no tener que darle a nadie un capón por decir que no existe un número primo que sea par. Y con las mismas me cojo y me voy, suerte con ello.

Amparo, ¿eres tú?

Amparo era la profesora de matemáticas discretas que es la rama de números enteros en la que se ve esto

Que tienes razón pero meh, empiezas en el tres y te olvidas

 

[Miembro eliminado 6516 Jorge2019]

Menos de un segundo

Lo acabaré poniendo pero vamos, yo hago un truco

Es pronto pero si, en un par de dias o asi lo subo para que todo el mundo pueda verlo

Uso Rust porque si usase C++ no se enteraba ni el apuntador Pero vamos, es parecido a Python, ya digo que hago lo básico, todos los numeros los pruebo con todos los que tengan por debajo

ya ya
dime como puedo ejecutar tu script
que no tengo ni puta idea

 

[Miembro eliminado 6516 Jorge2019]

Buenas sólo paso a recordaros que el 2 es par y es primo. Lo digo por no tener que darle a nadie un capón por decir que no existe un número primo que sea par. Y con las mismas me cojo y me voy, suerte con ello.

lo sabemos
y lo hemos tenido en cuenta

por alguna razón mi script es más lento si lo optimizo cribando los número pares

 

[Zollkron]

Amparo, ¿eres tú?

Amparo era la profesora de matemáticas discretas que es la rama de números enteros en la que se ve esto

Que tienes razón pero meh, empiezas en el tres y te olvidas

A partir del tres sí, pero no te dejes el dos porque si no tienes mal el algoritmo. No soy Amparo, no, pero si está buena preséntamela

 

[JC Denton]

ya ya
dime como puedo ejecutar tu script
que no tengo ni puta idea

No lo tienes porque lo que he subido es para animar a la gente, mañana te lo paso si es que no puedes esperar más. Lo que he subido si pulsas el boton rojo que pone "run" se ejecuta pero solo hay hasta el 100, es más para poner un ejemplo que otra cosa, le pondré un crono para que te diga los tiempos y asi comparas con tu misma máquina

Yo hago uso de cositas de lenguajes de viejos

 

[JC Denton]

A partir del tres sí, pero no te dejes el dos porque si no tienes mal el algoritmo. No soy Amparo, no, pero si está buena preséntamela

Era mayor, podía ser mi madre

Animate, se ve que sabes de mates asi que te medio defiendes, aunque sea con R, Sage o Matlab

 

[JC Denton]

lo sabemos
y lo hemos tenido en cuenta

por alguna razón mi script es más lento si lo optimizo cribando los número pares

No uses un rango, haz la suma manual de +=2 al final de cada iteración

Los rangos son "perezosos" y se calculan en tiempo real bajo demanda, es decir, que no son gratis

 

[Miembro eliminado 6516 Jorge2019]

No lo tienes porque lo que he subido es para animar a la gente, mañana te lo paso si es que no puedes esperar más. Lo que he subido si pulsas el boton rojo que pone "run" se ejecuta pero solo hay hasta el 100, es más para poner un ejemplo que otra cosa, le pondré un crono para que te diga los tiempos y asi comparas con tu misma máquina

Yo hago uso de cositas de lenguajes de viejos

soy el único que ha cumplido aquí
merezco un pajote

 

[Zollkron]

lo sabemos
y lo hemos tenido en cuenta

por alguna razón mi script es más lento si lo optimizo cribando los número pares

Eso es porque internamente, aunque tú le pongas un step 2 en el bucle, en ensamblador pasa por todos los números cuando el compilador lo desenrolla. Lo único que consigues con el step es poner más saltos.

 

[JC Denton]

soy el único que ha cumplido aquí
merezco un pajote

Hasta que no acaba la carrera no se sabe el ganador, Alonso lo sabe bien, de nada sirve ir primero si luego cruzas la meta cuarto como poco

 

[Zollkron]

Era mayor, podía ser mi madre

Animate, se ve que sabes de mates asi que te medio defiendes, aunque sea con R, Sage o Matlab

Yo ya estoy muy mayor para esto, me he pasado en plan jubilado que se pasa por la obra viendo como trabajáis la juventud

 

[JC Denton]

Eso es porque internamente, aunque tú le pongas un step 2 en el bucle, en ensamblador pasa por todos los números cuando el compilador lo desenrolla. Lo único que consigues con el step es poner más saltos.

Yo no quería entrar en tecnicismos pero es eso

Cuando el bucle se desenrolla se encuentra un range y el compilador no sabe lo que es eso o lo que va a generar porque como he dicho se calcula en tiempo de ejecución

Pero si pones el +=2 el compilador pillará el mensaje y desenrollará de forma correcta con lo que será más rápido


Asi que informático también eh, no seas flojo, ponte algo

 

[Zollkron]

Yo no quería entrar en tecnicismos pero es eso

Cuando el bucle se desenrolla se encuentra un range y el compilador no sabe lo que es eso o lo que va a generar porque como he dicho se calcula en tiempo de ejecución

Pero si pones el +=2 el compilador pillará el mensaje y desenrollará de forma correcta con lo que será más rápido


Asi que informático también eh, no seas flojo, ponte algo

Hay que dejar paso a la juventud. Vosotros venís con más ganas. Pero si os molan los piques de este tipo, pasaros por el UVa online judge, hay tenéis problemas algorítmicos para mediros las pollas todo lo que queráis. Sí tenéis curiosidad podéis ver mi perfil allí, también lo tengo en hackerrank otra web del estilo.