Determinar si un número dado es primo.
danmaster
01 de Septiembre del 2004
Imaginemos un programa que pide un número al usuario, sea el número que sea (real, positivo) nos devuelva un mensaje diciéndonos si es número primo o no.
Mi problema comienza con un algoritmo que utilicé para resolver este problema. Básicamente lo que hace es quedarse con el resto de dividir el número en cuestión entre 2, 3 y 5. Si ninguno de los restos es igual a 0, ese número es Primo.
Esto funciona con todos los números que he probado, pero sin embargo no existe ningun teorema que explique este razonamiento, y mi profesor de programación no me lo admite como bien, puesto que no puedo demostrar con una teorÃa razonada que se cumpla para todos los números hasta el infinito.
Alguien podrÃa pasarme un algoritmo que determine si un número es primo o no, sin usar mi método.
Y por su puesto no me vale eso de dividir ese número por todos los números hasta llegar a él. Me parece muy largo, aún eliminando los números pares...
Alguien me dice algo? gracias. XDDDD
Un saludo,
Dani
Mi problema comienza con un algoritmo que utilicé para resolver este problema. Básicamente lo que hace es quedarse con el resto de dividir el número en cuestión entre 2, 3 y 5. Si ninguno de los restos es igual a 0, ese número es Primo.
Esto funciona con todos los números que he probado, pero sin embargo no existe ningun teorema que explique este razonamiento, y mi profesor de programación no me lo admite como bien, puesto que no puedo demostrar con una teorÃa razonada que se cumpla para todos los números hasta el infinito.
Alguien podrÃa pasarme un algoritmo que determine si un número es primo o no, sin usar mi método.
Y por su puesto no me vale eso de dividir ese número por todos los números hasta llegar a él. Me parece muy largo, aún eliminando los números pares...
Alguien me dice algo? gracias. XDDDD
Un saludo,
Dani
ana
01 de Septiembre del 2004
hola
creo que puedes utilizar la funcion mod en las operaciones, no lo tengo en este momento, pero si quieres yo te lo mando mañana a tu correo. ok
creo que puedes utilizar la funcion mod en las operaciones, no lo tengo en este momento, pero si quieres yo te lo mando mañana a tu correo. ok
ana
01 de Septiembre del 2004
hola
creo que puedes utilizar la funcion mod en las operaciones, no lo tengo en este momento, pero si quieres mandame un correo, y yo te lo devuelvo con el algortimo, lo tengo en DFD si quieres te lo mando en este programa, o solo las lÃneas, ok
creo que puedes utilizar la funcion mod en las operaciones, no lo tengo en este momento, pero si quieres mandame un correo, y yo te lo devuelvo con el algortimo, lo tengo en DFD si quieres te lo mando en este programa, o solo las lÃneas, ok
Danmaster
01 de Septiembre del 2004
Si mandamelo al mail tio.
GRACIAS
Dani
GRACIAS
Dani
cjerk
01 de Septiembre del 2004
Tu algoritmos para determinar si un numero es primo o no viendo se un n Natural (no real) positivo mayor de 1 (no de 0) y que consiste en determinar si todos los restos son distintos de cero para ver si es primo es incorrecto.
En primer lugar porque cualquier numero producto de primos > 5 va a dar como resultado que todos esos que dices (al dividir por 2, 3 y 5) restos sean distintos de cero pero sin embargo ese numero no es primo (ya que como he dicho es producto de 2 primos).
Contraejemplo:
77 = 7*11 siendo 7 y 11 numeros primos
El resto de 77/2=1
El resto de 77/3=2
El resto de 77/5=2
Todos ellos distintos de cero y por lo tanto tu algoritmo diria que 77 es primo cuando no lo es.
Por esto no hay ningun teorema que diga esto.
Hay multitud de algoritmos para determinar si un numero es primo o no. Algunos deterministas y otros no deterministas. El algoritmo determinista mas sencillo es el que consiste en ir dividiendo por todos los anteriores. Este tipo de algoritmos es inviable para averiguar si numeros muy grandes son primos o no.
Hay algoritmos mucho mas sofisticados que dicen probabilisticamente si un numero es primo pero aqui ya nos metemos en cuestiones matematicas que no quieres saber.
Un saludo.
En primer lugar porque cualquier numero producto de primos > 5 va a dar como resultado que todos esos que dices (al dividir por 2, 3 y 5) restos sean distintos de cero pero sin embargo ese numero no es primo (ya que como he dicho es producto de 2 primos).
Contraejemplo:
77 = 7*11 siendo 7 y 11 numeros primos
El resto de 77/2=1
El resto de 77/3=2
El resto de 77/5=2
Todos ellos distintos de cero y por lo tanto tu algoritmo diria que 77 es primo cuando no lo es.
Por esto no hay ningun teorema que diga esto.
Hay multitud de algoritmos para determinar si un numero es primo o no. Algunos deterministas y otros no deterministas. El algoritmo determinista mas sencillo es el que consiste en ir dividiendo por todos los anteriores. Este tipo de algoritmos es inviable para averiguar si numeros muy grandes son primos o no.
Hay algoritmos mucho mas sofisticados que dicen probabilisticamente si un numero es primo pero aqui ya nos metemos en cuestiones matematicas que no quieres saber.
Un saludo.