En este articulo vamos a describir como resolver un problema que se nos suele presentar para desarrollar ciertas aplicaciones con python,pero el algoritmo se puede extrapolar a cualquier lenguaje, y es saber si un numero es primo, el articulo esta dividido en :
- El Problema
- La Solucion
- La Correccion
Los numeros primos son numeros que solo son divisibles entre 1 y entre ellos mismos, sabiendo esto podemos llegar a varias conclusiones y llegar a una solucion que nos resolvera nuestro problema.
El Problema
Saber si un numero es primo
La Solucion
Ser divisible entre un numero significa que al aplicar division entre ese numero el resto de la division debera ser 0 (cero). Para resolver este dilema haremos una serie de divisiones entre el numero en cuestion y todos los numeros antes de el incluyendolo a el mismo.
Entonces si para saber si el numero es primo solo deberemos poner un contador y se contador solo aumentara en caso de que la division entre cualquier numero de 0(cero), haciendo eso solo nos interesara que el resultado del contador sea 2. La division entre 1 y la division entre el mismo numero. siendo asi, el numero es primo, de lo contrario no lo es.
El codigo en python seria :
numero_leido = raw_input("inserta un numero >> ")
numero = int(numero_leido)
contador = 0
for i in range(1,numero+1):
if (numero% i)==0:
contador = contador + 1
if contador==2:
print "el numero es primo"
else print "el numero no es primo"
Hasta ahora se ha hecho todo un recorrido por todos los numeros desde 1 hasta el numero en cuestion, y se han hecho divisiones simultaneas hasta dar con el resultado.
La Correccion
Para corregir y hacer mas eficiente el algoritmo pues simplemente, si el numero es divisible tres 3 o mas veces el ciclo debe romperse y dar por hecho que el numero no es primo para verificar que hemos roto el ciclo declararemos una variable tipo Booleana la cual nos dira si es false, el numero es primo, y si es true el numero no es primo.
numero_leido = raw_input("inserta un numero >> ")
numero = int(numero_leido)
contador = 0
verificar= False
for i in range(1,numero+1):
if (numero% i)==0:
contador = contador + 1
if contador >= 3:
verificar=True
break
if contador==2 or verificar==False:
print "el numero es primo"
else: print "el numero no es primo"
Y siendo asi ya no haremos el recorrido de todos los numeros, solo bastara que el numero tenga tres divisores para concluir que no es primo.
