[C con Clase] Números primos en una matriz

[Steven Davidson]

Hola Cristian,

tACho XD Cristian Villota wrote:
> Hola a todos:
> 
> 
> Estoy intentando contar los números primos que se encuentran en una 
> matriz de [10][10]; pero cada vez que ejecuto el programa me indica
> un cero y parece que no los cuenta. El código que estoy utilizando es

A mí me da como resultado 1.

> el siguiente; si alguien capta el error le agradecería que me lo
> corrija:
> 

El problema está en que no usas 'cont' correctamente.

> 

[CORTE]

> 
>        for(c=1;c<=matriz[a][b];c++)
> {
> r=matriz[a][b]%c;
> if(r==0)
>  {
>   cont=cont+1;
>  }
> }

Aquí 'cont' sirve para contar las divisiones exactas con 'matriz[a][b]'. 
Como esta variable es un acumulador, debes asignarle 0 inicialmente 
antes de comenzar la prueba.

La solución es la siguiente:

cont = 0;

for( c=1; c<=matriz[a][b]; c++ )
{
   ...
}

De lo contrario, 'cont' continuará acumulando y por tanto contando todas 
las divisiones exactas, en lugar de contar todas de un número en 
particular: matriz[a][b]. Esto implica que 'cont2' tampoco contendrá una 
cuenta correcta. Por ejemplo, digamos que, 'matriz[0][0]' es 6; en la 
primera iteración obtendremos que,

¿ 6 % 1 == 0 ?  No  =>  cont = 0
¿ 6 % 2 == 0 ?  Sí  =>  cont = 1
¿ 6 % 3 == 0 ?  No  =>  cont = 0
¿ 6 % 4 == 0 ?  Sí  =>  cont = 2
¿ 6 % 5 == 0 ?  No  =>  cont = 0
¿ 6 % 6 == 0 ?  Sí  =>  cont = 3

Ahora llegamos a la condición para 'cont', que será,

¿ 3 <= 2 ?  No  =>  cont2 = 0

Como no reinicias el valor de 'cont', ésta seguirá acumulando por 
doquier. Esto implica que 'cont2' nunca será incrementado, porque 'cont' 
ya supera la cantidad de 2.

>        if(cont<=2)
> {
> cont2=cont2+1;
> }
> 
>      }
> 
>      printf("\n\t");
>    }
> 
>    printf("\n\n\n\tLos primos son: %d",cont2);
> 
> getch();
> 
> }
> 

Puedes optimizar un poco más este algoritmo para que no tenga que 
comprobar tantos números. Por ejemplo, no es necesario comprobar si 
'matriz[a][b]' es un múltiplo de 1, porque ya lo sabemos que lo es. 
Asimismo, no es necesario dividir 'matriz[a][b]' entre sí mismo, porque 
ya sabemos que lo es. Todos los enteros son divisibles entre 1 y sí mismo.

También sabemos que todos los números primos son impares excepto el 
número 2. Por lo tanto, sólo tenemos que comprobar los números impares. 
Para esto, recorremos la lista de divisores de dos en dos. Por ejemplo,


// Casos especiales: matriz[a][b] = 0, 1, ó 2
if( matriz[a][b] <= 2 )
{
   // es primo
}
else  // Caso general: matriz[a][b] > 2
   for( c=3; c<matriz[a][b]; c+=2 )
   { ... }

Existen muchas más optimizaciones, ya que hallar los números primos de 
una forma relativamente rápida es un problema popular, especialmente 
para la criptografía.

Dicho lo anterior, no se suele tomar en cuenta que 0 y 1 sean primos. En 
primer lugar, porque 0 no es divisible por sí mismo y en segundo lugar 
porque 1 ya es primo y realmente no hemos hallado nada nuevo.


Espero que esto aclare el tema.

Steven