Google+ Seguidores

sábado, 19 de abril de 2014

Numeros primos en python

    26

Numeros primos en python
Números primos en python
He visto que hay muchas consultas en la web relacionadas a ejercicios en python con números primos, ya sea ingresando un número y verificar que sea primo o saber cuantos números primos hay desde un número a otro. Voy a tratar de armar algunas soluciones a estos problemas para poder guiar u orientar a las personas que recién están  empezando a programar en python.


Los números primos: 

  • Son números naturales
  • Mayor que 1
  • Son divisibles por si mismos y por la unidad

Ejemplos:

  • 5 es primo, sus divisores son = (1, 5)
  • 6 es compuesto, sus divisores son  = (1, 2, 3, 6)
  • 7 es primo, sus divisores son 1 y 7
  • 8 es compuesto, sus divisores son 1, 2, 4 y 8

Determinar si un número es primo:

  • Pregunta: ¿El número 11 es primo?
  • Algoritmo: 
  • Tenemos que probar que el 11 no sea divisible entre los números del rango (2, 10)
  • Si el resto de dividir 11 entre (2, 3, 4, 5, 6, 7, 8, 9, 10) es 0, no es primo.
  • En este caso, el 11 no es divisible por ninguno de estos números, por lo tanto, es primo (solo es divisible entre el 1 y el mismo).

Nuestra primer funcion va a determinar si un numero determinado es primo o no:

#!/usr/bin/env python
# -*- coding: utf-8 -*-

#Números primos

def es_primo(num):
----if num < 2:     #si es menos que 2 no es primo, por lo tanto devolverá Falso
--------return False
----for i in range(2, num):  #un rango desde el dos hasta el numero que nosotros elijamos
--------if num % i == 0:    #si el resto da 0 no es primo, por lo tanto devuelve Falso
------------return False
----return True    #de lo contrario devuelve Verdadero

print es_primo(3)    #para probarlo llamamos a la función

Bien, ahora queremos saber cuantos numeros primos hay en un rango de numeros y cuales son. Podemos utilizar la primera funcion que creamos para que nos resulte mas facil la solucion:

def primos(num1, num2):  

----cont = 0
  
----for i in range(num1, num2):
--------if es_primo(i) == True: #Llamamos a la primera funcion para ahorrar trabajo ;)
------------cont += 1           #Que va a determinar si es primo o no
            ----print i               
  
----print ""  
----print "Hay", cont, "numeros primos" #Total de numeros primos
       
print primos(487, 8976)

Comentar que esta ultima funcion no es muy eficiente si el rango de numeros es muy grande, asi que los invito a crear alguna funcion que sea mas eficiente a la hora de buscar una gran cantidad de numeros primos. Espero esta entrada les sea de ayuda. Saludos, Diego.

26 comentarios:
Write comentarios
  1. pues si no haces el rango con los pares ya ahorraste la mitad de los números, sin contar que puedes hacer menos busquedas, pero bueno el aporte para los principiantes (y)

    ResponderEliminar
  2. Excelente, voy a probar tu consejo para ver como queda. Saludos

    ResponderEliminar
  3. Si no entiendo mal, Para ver si un número es par o no, lo que tenes que hacer es dividirlo por dos y verificar el resto, justo eso es lo que haces en la primera división de for (por dos) Ahi ya te sacaste de encima a todos los pares, ergo, no es tanto lo que ahorras.

    ResponderEliminar
    Respuestas
    1. Hola, para buscar numeros primos mas facil hice como me lo sugirio el primer comentario, saque todos los pares del rango. Hice una prueba de strees sobre la funcion (tiempo de ejecucion), y si se nota la diferencia de tiempo cuando son muchos numeros. Saludos

      Eliminar
  4. Si mirais desde la raiz del número cuadrada hacia abajo ganais más tiempo...

    ResponderEliminar
  5. Además, es mejor aprovechar las reglas de divisibilidad matemática, pues ahorra muchísimo (pero muchísimo).
    Espero luego aportar un código de uno que tenía en C++ que había hecho como reto de programación eficiente y está optimizado: calculaba cientos de miles en pocos segundos en una mini laptop! Lo buscaré y lo pasaré a python con lo que he aprendido acá para aportar como mi "¡gracias por el blog!".

    ResponderEliminar
    Respuestas
    1. Muy bueno, espero pronto puedas pasar el código así lo agrego a la entrada. Y gracias a ti por visitar el blog. Saludos

      Eliminar
  6. el número 2 también es un número primo entonces en tu sentencia -if num % i == 0, si pones 2 lo considera como un número no primo ya que 2%2=0

    ResponderEliminar
  7. Implementación de la criba de Atkin, usando Numpy.

    Gist: http://bit.ly/1w3E2bY

    $ time python atkin.py 100000
    ...
    real 0m2.716s
    user 0m2.593s
    sys 0m0.030s

    En una netbook ASUS Eee PC con Intel Atom CPU N570 @ 1.66GHz.

    ResponderEliminar
    Respuestas
    1. Quería ver si es mas rápido con Numpy pero se lo quite y es mas rápido en puro Python, al menos en mi caso:

      $ time python atkin.py 100000
      ...
      real 0m2.024s
      user 0m1.923s
      sys 0m0.007s

      Eliminar
    2. Acabo de portar el código anterior de Python a Julia (me tomo 5 minutos), aumente el limite a un millón y los resultados son realmente sorprendentes! :D

      Gist: http://bit.ly/146pL7I

      julia> include("atkin.jl")
      criba_atkin (generic function with 1 method)

      julia> limite = 1000_000
      1000000

      julia> @time criba_atkin(limite);
      elapsed time: 0.384810373 seconds (10187968 bytes allocated, 15.34% gc time)

      julia> @time criba_atkin(limite);
      elapsed time: 0.164980531 seconds (9602852 bytes allocated)

      julia> @time primes(limite);
      elapsed time: 0.206970021 seconds (441812 bytes allocated)

      julia> criba_atkin(limite) == primes(limite)
      true

      Eliminar
    3. Excelente Ismael, en la noche lo miro para ver como funciona, tiene muy buena pinta ;) Saludos

      Eliminar
  8. como puedo saber los números primos mayores o iguales a un numero que yo ingreso por input?

    ResponderEliminar
    Respuestas
    1. Hola, has pensado alguna solución para resolver el problema? Saludos

      Eliminar
    2. he tratado de hacerla con un while, un if y un for, pero con ninguna he llegado a una solución concreta...no se como hacer que me imprima el numero primo que le sigue.
      gracias...URGENTE.

      Eliminar
    3. si sabes como hacerlo, podrías pasarme el código?

      Eliminar
    4. Hola, yo no resuelvo tareas y menos de carácter URGENTE. Haciendo alguna modificación en el código que propuse en la entrada puedes solucionar tu inconveniente. Si quieres aprender a programar vas a tener que practicar. Saludos

      Eliminar
  9. estos de los primos es todo un tema...
    había escrito algo asi

    def lista(a):
    lista=[2,3,5 ]
    c=int(range(sqrt(a)))
    if x%2!=0 or x%3!=0 or x%5!=0:
    lista.append(x)
    return (lista)

    def primo(a):
    lista(a)
    from x in lista:
    if a%x==0:
    print (str(a)+" NO es primo")
    else:
    print (str(a)+" SI es primo")

    creo q era algo asi...
    como lo ven?

    ResponderEliminar
  10. me borro las sangrías :(
    ah, me olvide de aclarar >5

    ResponderEliminar
  11. por ultimo, muy buen lugar, lo poco q he visto me ha servido!!!

    ResponderEliminar
    Respuestas
    1. Hola, Gracias por visitar el blog y participar. Las sangria las quita si, yo aveces pongo 4 ---- para hacer una tabulación. Luego reviso tu código. Saludos ;)

      Eliminar
  12. Alguien sabe como hacer un programa para calcular números cuadrados de los primos.

    ResponderEliminar
  13. Tengo gratos recuerdos de este problemas, porque fue el primer problema serio que me propuse cuando estaba comenzando :)
    Te doy una pista de como lo resolví yo: tienes que incluir un grupo de sentencias (dentro del bucle) que te permitan reducir progresivamente el rango de números a probar.. Te pregunto ¿siendo m y n cualesquiera números enteros positivos y mayores que cero, se puede efectuar {n / ((n/2) + m)} y obtener un resultado entero? El tema de los primos es apasionante, y aunque debe haber mejores soluciones que la mía, quizá te pueda ayudar a optimizar un poquito el tiempo de ejecución. Saludos.

    ResponderEliminar
  14. Prueben eset codigo para ver los n primeros numeros primos, espero que les sirva de ayuda


    public static void Primos()
    {
    Console.WriteLine("Cuantos primos quiere conocer");
    int max = int.Parse(Console.ReadLine());
    int [] vPrimo = new int[max];
    int [] vTemp = new int[4]{11,3,7,9};
    int i = 0;
    int i2 = 1;
    int hasta;
    Console.WriteLine("Los Primos a partir de 3 son:");
    while(true)
    {
    if(vPrimo[i] == 0)
    {
    vPrimo[i] = vTemp[i2];
    Console.WriteLine( i+" "+vTemp[i2]);
    vTemp[i2] += 10;
    if (i + 1 == max)
    break;

    }

    i2 += 1;
    if(i2 == 4)
    i2 = 0;
    hasta = vTemp[i2]/2;
    foreach(int p in vPrimo)
    {
    if(p == 0)
    {
    i+=1; break;
    }
    else if(p <= hasta)
    {
    if(vTemp[i2]%p == 0)
    {
    vTemp[i2] += 10;
    break;
    }
    }
    else {
    i+=1; break;
    }
    }

    }

    }

    ResponderEliminar
    Respuestas
    1. Excelente, hoy lo pruebo para ver que tal. Saludos y gracias por compartir ;)

      Eliminar
  15. Sin ser experto en matematicas (pues se que hay maneras complejas y eficientes de calcular que un numero primo, yo hago algo parecido a lo propuesto en el post, pero sin generar lista. Reviso básicamente dos condiciones: si el numero es par, si el numero es un cuadrado perfecto. Si se quiere calcular un rango de numeros luego se puede hacer un for. Creo que es ligeramente mas eficiente que generar la lista desde el principio:

    from math import sqrt

    def CalculaCuadradoPerfecto(num):
    # devuelve verdadero si el numero es un cuadrado perfecto
    res = int(sqrt(num))
    if num % res == 0:
    return True
    else:
    return False


    def CalculaPrimo(num):
    # Devuelve Verdadero si el numero es primo
    if num is 2:
    return True
    elif num % 2 == 0:
    return False
    elif CalculaCuadradoPerfecto(num):
    return False
    else:
    check = 3
    while check < num:
    if num % check == 0:
    return False
    check += 2
    return True

    ResponderEliminar

Tu comentario es importante y nos motiva a seguir escribiendo...

Entradas más recientes

© 2014 Mi diario Python. Designed by Bloggertheme9 | Distributed By Gooyaabi Templates
Powered by Blogger.