Título: (Duda matemática) Cuestión sobre los números primos Publicado por: class_OpenGL en 6 Mayo 2016, 02:50 am Hola, muy buenas. Tengo una duda que se podría catalogar como matemática más que duda de programación.
El caso es que la manera que he visto más eficiente para saber si un número es primo en C es la siguiente: (Código corregido) Código
Mi duda es: ¿Por qué solo comprobamos los posibles divisores del número a comprobar con la condición 'j*j <= numero_a_comprobar'? Seguro que tiene una respuesta matemática, pero no la se... Muchas gracias Título: Re: (Duda matemática) Cuestión sobre los números primos Publicado por: xiruko en 6 Mayo 2016, 04:43 am Hola,
De dónde sale esa i? Código
Saludos! Título: Re: (Duda matemática) Cuestión sobre los números primos Publicado por: class_OpenGL en 6 Mayo 2016, 05:01 am Disculpad. Es que adapté el código que tenía. La 'i' es el número a comprobar.
Código corregido: Código
Título: Re: (Duda matemática) Cuestión sobre los números primos Publicado por: arget en 6 Mayo 2016, 12:04 pm Bueno, quizá sea el más eficiente desde la fuerza bruta, porque el más eficiente es la "criba general del cuerpo de números".
Por otro lado, veo un pequeño problema en la parte de la presentación, por lo menos usa paréntesis para que quede más claro todo, en lugar de: Código: for(j = 2; is_prime == 1 && j*j <= numero_a_comprobar; j++) Código: for(j = 2; (is_prime == 1) && (j*j <= numero_a_comprobar); j++) Luego, siempre me ha hecho gracia usar los operadores "==" y "!=" fuera de un if o for, sin embargo hay que reconocer que es poco comprensible, y al final se supone que perseguimos la legibilidad del código. Si usaras Código: if(numero_a_comprobar % j != 0) De todas formas, yo creo que puede hacerse más simple sin perder eficiencia. Título: Re: (Duda matemática) Cuestión sobre los números primos Publicado por: class_OpenGL en 6 Mayo 2016, 15:01 pm Los operadores de comparación (como '==' y '!=') tienen preferencia sobre los lógicos (como '&&').
Yo estoy acostumbrado a este tipo de notación, así que no me percaté que podría ser poco legible para los que no lo están. Lo siento. En cualquier caso, veo que se ha entendido cuál es la duda, así que si alguien es tan amable de responder, le estaría agradecido :D Título: Re: (Duda matemática) Cuestión sobre los números primos Publicado por: MK-Ultra en 6 Mayo 2016, 15:05 pm En cuanto a tu duda original, cuando se busca saber si un número es primo no tiene sentido buscar divisores mayores a la raiz cuadrada del número.
El motivo de esto es el siguiente: Supongamos que quiero saber si n es un número primo. Lo que voy a hacer será empezar a probar por j=2 si el resto de dividir n por 2 es 0 y así iterando en j. Ahora, consideremos lo que ocurre cuando j=parte_entera(raiz_cuadrada(n))+C (C siendo una constante entera positiva cualquiera). Para que j sea divisor de n, debe existir un k entero tal que se cumpla n = j*k Ahora bien, este k no puede ser cualquier número, debe ser menor a j. Por qué? Porque si k fuese igual a j estariamos en el caso de C = 0, lo que haría j a la raiz cuadrada de n y ese caso ya está contemplado. Si k fuese mayor a j, y j es mayor a la raiz cuadrada de n, entonces claramente como j*j > n se cumple que k*j > n. De modo que a k no le queda otra que ser menor a j. Pero como k es menor a j, y k es divisor de n por definición, de existir k ya lo habría encontrado en una iteración previa. De modo que k no existe si j es mayor a la raiz cuadrada de n. Espero que se entienda, cualquier cosa me preguntás. Saludos! Título: Re: (Duda matemática) Cuestión sobre los números primos Publicado por: class_OpenGL en 6 Mayo 2016, 15:31 pm Sinceramente, aunque he entendido la idea final de tu explicación, no me he enterado de algunas cosas.
Lo que me ha hecho comprender lo que querías decir es lo siguiente: Código: Para que j sea divisor de n, debe existir un k entero tal que se cumpla n = j*k ¡MUCHAS GRACIAS! Título: Re: (Duda matemática) Cuestión sobre los números primos Publicado por: MK-Ultra en 6 Mayo 2016, 15:53 pm Me alegra que al final hayas entendido, cualquier duda que te haya quedado por el medio podés preguntar, prometo que no muerdo.
Título: Re: (Duda matemática) Cuestión sobre los números primos Publicado por: class_OpenGL en 6 Mayo 2016, 16:03 pm Jajaja. No, de verdad, me ha quedado superclaro. Tanto, que he podido resolver un ejercicio que me tenía desconcertado en el que tenía que usar estos conceptos.
De verdad, ¡MUCHAS GRACIAS! Título: Re: (Duda matemática) Cuestión sobre los números primos Publicado por: MinusFour en 6 Mayo 2016, 16:18 pm Es más fácil si piensas en los posibles factores de los números:
16: 1 x 16 2 x 8 4 x 4 8 x 2 16 x 1 9: 1 x 9 3 x 3 9 x 1 15: 1 x 15 3 x 5 5 x 3 15 x 1 30: 1 x 30 2 x 15 5 x 6 6 x 5 15 x 2 30 x 1 Como puedes ver los factores se repiten después de la raíz cuadrada del número y como al dividir el número entre otro número j también incluye el resultado como factor posible de n, terminas descartando dos números en lugar de uno. |