(Duda matemática) Cuestión sobre los números primos

[class_OpenGL]

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 (c) [Seleccionar] Expandir

unsigned int is_prime = 1, numero_a_comprobar = 2453564567U;

for(j = 2; is_prime == 1 && j*j <= numero_a_comprobar; j++)
   is_prime = numero_a_comprobar%j != 0;

// Ahora 'is_prime' almacena si 'numero_a_comprobar' es primo

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

[xiruko]

Hola,

De dónde sale esa i?

Código (c) [Seleccionar] Expandir

is_prime = i%j != 0;

Saludos!

[class_OpenGL]

Disculpad. Es que adapté el código que tenía. La 'i' es el número a comprobar.

Código corregido:

Código (c) [Seleccionar] Expandir

unsigned int is_prime = 1, numero_a_comprobar = 2453564567U;

for(j = 2; is_prime == 1 && j*j <= numero_a_comprobar; j++)
    is_prime = numero_a_comprobar%j != 0;

// Ahora 'is_prime' almacena si 'numero_a_comprobar' es primo

[arget]

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 [Seleccionar] Expandir

for(j = 2; is_prime == 1 && j*j <= numero_a_comprobar; j++)
Podrías poner

Código [Seleccionar] Expandir

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 [Seleccionar] Expandir


if(numero_a_comprobar % j != 0)
    is_prime = 1;
else
    is_prime = 0;

apenas se traduce en cuatro instrucciones más en ensamblador, no se pierde en eficiencia y se gana en legibilidad.

De todas formas, yo creo que puede hacerse más simple sin perder eficiencia.

[class_OpenGL]

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

[MK-Ultra]

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!

[class_OpenGL]

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 [Seleccionar] Expandir

Para que j sea divisor de n, debe existir un k entero tal que se cumpla n = j*k

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.

¡MUCHAS GRACIAS!

[MK-Ultra]

Me alegra que al final hayas entendido, cualquier duda que te haya quedado por el medio podés preguntar, prometo que no muerdo.

[class_OpenGL]

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!

[MinusFour]

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.