Práctico 5 - Ejercicio 7

Práctico 5 - Ejercicio 7

de Alexis Sokorov Vargas -
Número de respuestas: 1

Buenas, tengo una duda con la solución del ejercicio:


¿Cuál es el sentido de inicializar a fin como \text{trunc(sqrt(numero))} y por qué se lo compara con divisor para poder entrar al while o evaluarlo en los if que le siguen a éste?

En respuesta a Alexis Sokorov Vargas

Re: Práctico 5 - Ejercicio 7

de Guillermo Rey Martusciello -
Buenas Alexis, todo bien?

Contexto:

Definicion numero primo: numero natural, tal que sus unicos divisores naturales son 1 y el mismo.

Se evalua "numero mod divisor" incrementando divisor hasta raiz cuadrada de num (como maximo) por la siguiente razon:

En este ejercicio intentamos encontrar un numero natural n que divida a num (sin ser este ni 1 ni num) para probar que un numero NO es primo. Si se da que probamos con numeros hasta la raiz cuadrada de num y ninguno lo divide, podemos afirmar que es primo (explico el por que de esto mas adelante).

Si n efectivamente divide a num, entonces: num = n * m (notese que m tambien divide a num). Si se da esto, alguno de los dos (m o n) es menor o igual que sqrt(num) (si los dos son mayores que sqrt(num) su multiplicacion daria mayor que num). Sin perdida de generalidad digamos que n <= m, por lo tanto n <= sqrt(num).

Como solo nos interesa saber si hay ALGUN divisor de num basta con encontrar n y lo podemos encontrar calculando “num modulo x” para todos los valores anteriores a sqrt(num), si alguno da 0, entonces ese numero divide a num.

Luego, se hace el trunc porque estamos buscando divisores naturales.

Lo que hace el while es: mientras el divisor no divida a num y no me haya excedido de la raiz cuadrada de num, incremento en uno divisor para probar suerte con el siguiente posible divisor.

Despues del while se pregunta si divisor <= fin. Si esto es verdadero significa que corte la ejecucion del while porque num mod divisor era igual a cero => divisor divide al numero => el numero no es primo. En caso de que sea falso es que me pase de la raiz cuadrada del numero y no encontre ningun divisor.

Si queda alguna duda sobre la respuesta no dudes en consultar de nuevo, te recomiendo que le pegues varias leidas porque hay mucho detalle sutil.


Saludos,
Guille