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
- 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
- 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.
-
Anónimo dice: 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.
-
PythonDiario dice:
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
-
-
Anónimo dice:
Si mirais desde la raiz del número cuadrada hacia abajo ganais más tiempo...
-
Anónimo dice:
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!".-
PythonDiario dice:
Muy bueno, espero pronto puedas pasar el código así lo agrego a la entrada. Y gracias a ti por visitar el blog. Saludos
-
-
Anónimo dice:
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
-
Unknown dice:
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.030sEn una netbook ASUS Eee PC con Intel Atom CPU N570 @ 1.66GHz.
-
Unknown dice:
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 -
Unknown dice:
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! 😀
Gist: http://bit.ly/146pL7I
julia> include("atkin.jl")
criba_atkin (generic function with 1 method)julia> limite = 1000_000
1000000julia> @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 -
PythonDiario dice:
Excelente Ismael, en la noche lo miro para ver como funciona, tiene muy buena pinta 😉 Saludos
-
-
Anónimo dice:
como puedo saber los números primos mayores o iguales a un numero que yo ingreso por input?
-
Anónimo dice:
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. -
PythonDiario dice:
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
-
Unknown dice:
# -*- coding: utf-8 -*-
"""
Decir que esta hecho en Python 3.X.XCreated on Fri Oct 6 10:58:05 2017
@author: 21711787
"""numero= int(input("¿Qué número quieres que analize?, escríbelo: "))
valor= range(2,numero)
contador = 0
for n in valor:
if numero % n == 0:
contador +=1
print("divisor:", n)if contador > 0 :
print(f"El número {numero} no es primo")
else:
print(f"El nÚmero {numero} es primo")
-
Anónimo dice:
estos de los primos es todo un tema...
había escrito algo asidef 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? -
-
PythonDiario dice:
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 😉
-
-
Anónimo dice:
Alguien sabe como hacer un programa para calcular números cuadrados de los primos.
-
Anónimo dice:
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. -
Anónimo dice:
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;
}
}}
}
-
PythonDiario dice:
Excelente, hoy lo pruebo para ver que tal. Saludos y gracias por compartir 😉
-
-
Unknown dice:
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 Falsedef 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 -
Anónimo dice:
como hacer que dentro de un rango de numeros te saque dos numeros primos aleatoriamente
-
PythonDiario dice:
Hola!!! Has podido hacer algo? en que parte te trancas?
Saludos y gracias por visitar el blog!!!
-
-
Francisco García Sanz dice:
En el algoritmo de determinar si un número N es primo no hay que dividir entre todos los números hasta el N-1 ya que entre N/2 y N nunca hay divisores. Nos ahorramos la mitad del bucle
-
Roberto dice:
Aunque veo que todo esto viene de muy antiguo,(Yo estoy aprnediendo Python en 2019). Os copio y pego el archivo que tengo sobre esto de calcular primos, divisores, primo siguiente
a un número dado y lista de siguientes a un numero dado.
Quizás alguno pueda sacar provecho.from math import sqrt
#CALCULO DE LOS DIVISORES DE UN NUMERO
m=int(input ("Dime el numero del que quieres sus divisores: "))
def divisores (m):
listad=[]
for i in range(1,m//2):
i+=1
if m%i==0:
listad.append(i)
return listad
print(divisores(m))#CALCULO DE SI UN NUMERO ES O NO PRIMO
n=0
n=int(input ("Dame el numero para ver si es primo "))
def primo(n):primin=True
i=1
while (primin and i<=sqrt(n)):
if n==2 or n==3:
break
i+=1
if n%i==0:
primin=False
break
return primin
print(primo(n))#Calcular el número primo, siguiente a un numero dado.(Aunque éste no sea primo o incluso par)
n=0
n=int(input("Dame el numero anterior al que tu quieres calcular "))
def sigup(n):
#n=int(input("Dame el numero anterior al que tu quieres calcular "))
if n%2==0:
n=n-1
n+=2
while not primo(n):
n+=2
return n
print(sigup(n))#Calcular una lista de números primos a partir de uno dado. Aunque éste no sea primo o incluso si es par.
p=0
q=0
def listp(p,q):
p=int(input("Dime el numero de elementos de la lista "))
q=int(input("Y el número a partir del cual, quieres la lista "))
if q<=2:
lista=[2,3]
else:
lista=[q]
if q%2==0:
q+=1
lista=[q]
if not primo(q):
lista=[sigup(q)]
i=sigup(q)
else:
i=q
while len(lista)<p:
lista.append(sigup(i))
i=sigup(i)
return lista
print(listp(p,q)) -
Roberto dice:
Veo que al publicarlo ha quitado todas las sangrías, si alguno quiere ver como funciona que me avise por aquí y se lo envío por email.
-
Roberto dice:
ccinfo3131, mi correo es robervillaescusa@gmail.com
Si quieres que te envíe lo que tengo dame tu email y te lo preparo. He seguido avanzando para que trabajar con números mas grandes o sea que trabaje mas rápido.
Si lo quieres pídemelo a través de ese mi correo.
-
Pagarus dice:
from math import sqrt
inicial = int(input ('ingrese inicio del rango a evaluar: '))
limite = int(input('ingrese final del rango a evaluar: '))
for i in range (inicial, limite):
esPrimo = True
divisor = 2
while esPrimo and divisor <= int (sqrt(i)):if i % divisor == 0:
esPrimo = False
else:
divisor += 1
if esPrimo:
print (i) -
El Universo de los Links dice:
# Determinar Cuantos Números Primos hay en un Rango de Números :
y = int(input("Ingrese Número Inicial : "))
x = int(input("Ingrese Número Final : "))
c = 0
for n in range(y, x + 1):
d = 0
for i in range(1 , n + 1):
if n % i == 0:
d = d + 1
if d == 2:
c = c + 1
print(n,end=" ")print(f"-------> Hay : {c} números primos")
-
Christian dice:
Qué les parece eso ? Imprime los números primos hasta ek número que se le indique. Lo optimicé.
def Imprimir_Primos():
Lista=[2]
Candidato=3
cantidad=1
while Candidato<=100000000:
Es_Primo=True
indice=0
while Es_Primo and indice<cantidad and Lista[indice]<Candidato/Lista[indice]:
if Candidato%Lista[indice]==0:
Es_Primo=False
indice=indice+1
if Es_Primo:
print(Candidato)
Lista.append(Candidato)
cantidad=cantidad+1
Candidato=Candidato+2Imprimir_Primos()
PythonDiario 
jose Deja una respuesta
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)