[C con Clase] Errores de aprendiz

[Steven Davidson]

Hola Ariel,

Ariel Tarifeño wrote:
> Gracias Steven. Me ayudo mucho. Sii, del N° 13 en adelante daba
> siempre error. Lo cambie y funciona aunque sigue siendo de
> principiante.
>  

Bueno, lo que podemos hacer es modificar tu algoritmo original para no 
introducir errores. Como realmente no quieres calcular el factorial de 
'N-1', sino que es un paso para el problema de verdad: determinar si 'N' 
es primo o no, entonces podemos realizar los cálculos con operaciones de 
módulo. De esta forma, podemos hacer el cálculo del módulo en tu fórmula 
por "piezas" o por términos; o sea, de una manera discreta en lugar de 
hacer todo de golpe.

Algunas propiedades de operaciones de módulo son las siguientes:

1. (x+y) mod n = (x mod n + y mod n) mod n
2. (x*y) mod n = ((x mod n) * (y mod n)) mod n

Por ejemplo,

15 mod 4 = 3

1. (10+5) mod 4 = (10 mod 4 + 5 mod 4) mod 4 = (2+1) mod 4 = 3
2. (5*3) mod 4 = ((5 mod 4) * (3 mod 4)) mod 4 = (1*3) mod 4 = 3

Con estas dos propiedades, podemos separar las operaciones de tu 
algoritmo para no tener que calcular el factorial total, sino su 
contribución al cálculo final de 'mod N'. Esto sería,

((N-1)! + 1) mod N = 0 ?

pasa a ser,

((N-1)! mod N + 1) mod N = 0 ?  Ten presente que 1 mod N = 1

Como el factorial es una serie de multiplicaciones, entonces podemos 
aplicar la propiedad #2 en un bucle 'for'. Sin embargo, podemos 
optimizar un poco esto, ya que los factores de '(N-1)! mod N' siempre 
serán menores que 'N'. Es decir,

(N-1)! mod N;
((N-1) mod N) * ((N-2)! mod N)) mod N;
((N-1) * ((N-2)! mod N)) mod N
...

O sea,
N-1 < N  =>  (N-1) mod N < N
N-2 < N  =>  (N-2) mod N < N
N-3 < N  =>  (N-3) mod N < N
...

Por lo tanto, no tenemos que calcular el módulo de cada factor, pero sí 
tenemos que hacerlo para cada pareja de factores. Con esto, podemos 
sacar una relación recurrente:

res[2] = ((N-1) * (N-2)) mod N  (caso base o inicial)
res[3] = (res[2] * (N-3)) mod N
res[4] = (res[3] * (N-4)) mod N
...
res[n] = (res[n-1] * (N-n)) mod N, donde n=3,4,...,N-1

No recomiendo implementar este algoritmo como una función recursiva, 
sino iterativamente; o sea, usa un bucle 'for'.

Al final, agregaríamos 1 al valor final de 'res', por lo que tendríamos 
aplicar nuevamente el cálculo del módulo:

res_final = (res+1) mod N

Lo último  que queda por hacer es comprobar si 'res_final' es 0 (cero) o 
no, para determinar si 'N' es primo o no.


Huelga decir que las limitaciones de 'int' siguen siendo las mismas que 
en el algoritmo anterior, pero al no tener que hacer multiplicaciones 
con números grandes, podemos alcanzar un valor de 'N' mayor al que 
podíamos antes. Si 'int' es de 32 bits, entonces podemos usar valores de 
N <= 65536; con 'int' de 64 bits, el alcance es de N <= 9223372036854775808.

Espero que todo esto te sirva.

Steven