elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Únete al Grupo Steam elhacker.NET


+  Foro de elhacker.net
|-+  Foros Generales
| |-+  Dudas Generales (Moderador: engel lex)
| | |-+  (Duda matemática) Cuestión sobre los números primos
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: (Duda matemática) Cuestión sobre los números primos  (Leído 2,240 veces)
class_OpenGL


Desconectado Desconectado

Mensajes: 437

Si usas Direct3D, no eres mi amigo :P


Ver Perfil
(Duda matemática) Cuestión sobre los números primos
« 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
  1. unsigned int is_prime = 1, numero_a_comprobar = 2453564567U;
  2.  
  3. for(j = 2; is_prime == 1 && j*j <= numero_a_comprobar; j++)
  4.    is_prime = numero_a_comprobar%j != 0;
  5.  
  6. // 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


« Última modificación: 6 Mayo 2016, 05:01 am por class_OpenGL » En línea

Programador aficionado. Me quiero centrar en programar videojuegos. La API que uso para crearlos es OpenGL
xiruko


Desconectado Desconectado

Mensajes: 437


Ver Perfil
Re: (Duda matemática) Cuestión sobre los números primos
« Respuesta #1 en: 6 Mayo 2016, 04:43 am »

Hola,

De dónde sale esa i?

Código
  1. is_prime = i%j != 0;

Saludos!


En línea

class_OpenGL


Desconectado Desconectado

Mensajes: 437

Si usas Direct3D, no eres mi amigo :P


Ver Perfil
Re: (Duda matemática) Cuestión sobre los números primos
« Respuesta #2 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
  1. unsigned int is_prime = 1, numero_a_comprobar = 2453564567U;
  2.  
  3. for(j = 2; is_prime == 1 && j*j <= numero_a_comprobar; j++)
  4.    is_prime = numero_a_comprobar%j != 0;
  5.  
  6. // Ahora 'is_prime' almacena si 'numero_a_comprobar' es primo
En línea

Programador aficionado. Me quiero centrar en programar videojuegos. La API que uso para crearlos es OpenGL
arget

Desconectado Desconectado

Mensajes: 44


Ver Perfil
Re: (Duda matemática) Cuestión sobre los números primos
« Respuesta #3 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++)
Podrías poner
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)
    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.
En línea

La gestión manual de bloques de memoria en C es como hacer malabarismos con pastillas de jabón en la ducha de la prisión: todo diversión hasta que cometes un fallo.
class_OpenGL


Desconectado Desconectado

Mensajes: 437

Si usas Direct3D, no eres mi amigo :P


Ver Perfil
Re: (Duda matemática) Cuestión sobre los números primos
« Respuesta #4 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
En línea

Programador aficionado. Me quiero centrar en programar videojuegos. La API que uso para crearlos es OpenGL
MK-Ultra


Desconectado Desconectado

Mensajes: 435


~ Nevermind ~


Ver Perfil WWW
Re: (Duda matemática) Cuestión sobre los números primos
« Respuesta #5 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!
En línea

Agradecer no cuesta nada (al menos no mucho)

BTC: 1DHKsWE6wGkUiHbKkwBDaF8DEGwn9n6nxQ
class_OpenGL


Desconectado Desconectado

Mensajes: 437

Si usas Direct3D, no eres mi amigo :P


Ver Perfil
Re: (Duda matemática) Cuestión sobre los números primos
« Respuesta #6 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

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!
En línea

Programador aficionado. Me quiero centrar en programar videojuegos. La API que uso para crearlos es OpenGL
MK-Ultra


Desconectado Desconectado

Mensajes: 435


~ Nevermind ~


Ver Perfil WWW
Re: (Duda matemática) Cuestión sobre los números primos
« Respuesta #7 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.
En línea

Agradecer no cuesta nada (al menos no mucho)

BTC: 1DHKsWE6wGkUiHbKkwBDaF8DEGwn9n6nxQ
class_OpenGL


Desconectado Desconectado

Mensajes: 437

Si usas Direct3D, no eres mi amigo :P


Ver Perfil
Re: (Duda matemática) Cuestión sobre los números primos
« Respuesta #8 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!
En línea

Programador aficionado. Me quiero centrar en programar videojuegos. La API que uso para crearlos es OpenGL
MinusFour
Moderador Global
***
Desconectado Desconectado

Mensajes: 5.213


I'm fourth.


Ver Perfil WWW
Re: (Duda matemática) Cuestión sobre los números primos
« Respuesta #9 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.
« Última modificación: 6 Mayo 2016, 17:11 pm por MinusFour » En línea

Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines