Problema de comprensión programa C

Iniciado por ruby, 3 Octubre 2021, 13:47 PM

0 Miembros y 1 Visitante están viendo este tema.

ruby

Buenas,
tengo que solucionar un problema de un programa en C cuyo objetivo es calcular los números del 1 al 20. El problema es que devuelve los números 9, 11, 13, 15, 17 y 19 cuando la salida debería ser 2, 3, 5, 7, 11, 13, 17, 19.

Lo sé, es un programa ridículamente fácil pero llevo desde 1º de carrera sin tocar C (los últimos años he estado trabajando en Java) y estoy muy perdida con los conceptos básicos, así que estoy bastante jodida porque este programa nos lo han dado para recordar C, pero la asignatura es Sistemas Operativos y tendré que hacer movidas curiosas...

En fin, no entiendo las expresiones subrayadas en negrita. Aunque agradecería que alguien me explicara al completo el funcionamiento de la función es_primos porque he estado usando el depurador para ver si me aclaraba y ha sido peor aún. Por ejemplo, cuando p=1, sale del bucle for cuando f toma el valor 5 (es decir, se ejecuta solo 2 veces y no entiendo por qué... Realmente no veo la condición de salida del for). Por otra parte, en la primera expresión marcada en negrita yo entiendo que es: A p se le asigna el valor del resto resultante de la división p:2 siempre que dicho resto sea distinto de 0. Pero en la práctica no veo que sea así.

/* Programa que calcula primos */

#include <stdio.h>
#include <math.h>

/*  Función es_primo (int p)
    p   parámetros de entrada. Número a evalurar si es primo
    Devuelve:
        0   Si p no es primo
        1   Si p es primo

    Para ver si un número es primo se intenta dividir por todos sus posibles divisores.
    Si alguno da resto cero, entonces no es primo
*/   
int es_primo ( int p );

int main ( void )
{
   const int MIN = 1;   /* Primer nº que evalúa si es primo */
   const int MAX = 20; /* Último nº que evalúa si es primo */
   int primo;          /* Recorre los posibles primos en el rango [MIN,MAX] */

   for ( primo = MIN; primo <= MAX; primo = primo + 1 )
      if ( es_primo ( primo ) )
         fprintf ( stdout, "%d\n", primo );
   return 0;
}

int es_primo ( int p )
{
   const int MAXFACTOR = ( int ) (sqrt ( (double)p )); /* Máximo factor posible de p */
   int f; /* Factor por el que se va comprobando si p es divisible */
   int primo; /* 1 Si p no es divisible por ningún f probado y 0 en caso contrario */

   primo = ( ( p % 2 ) != 0 );
   for ( f = 3; primo && ( f > MAXFACTOR ); f = f + 2 )
      primo = ( ( p % f ) == 0 )
   return primo;
}



MAFUS

Realmente podrías haber resuelto esta función cómo si estuvieras en Java, no hay mucha diferencia. Pero debo decir que sí, tu algoritmo para es_primo es erróneo.

Una solución sería esta:
int es_primo ( int p ) {
   int divisor;

   /* Casos base */
   /* Falta por decidir qué se hace con los números menores de 1 */
   if( p == 1 )    return 0;     /* El 1 no se considera primo. */
   if( p == 2 )    return 1;     /* El 2 se considera primo.    */
   if( p & 1 == 0) return 0;  /* Ningún par, a excepción del 2 (controlado anteriormente) es primo. */

   for(divisor = 3; divisor * divisor <= p; divisor += 2) { /* Se usará el divisor a partir del tres, con incremento de 2 (así se evita operar con pares) */
      if ( p % divisor == 0)                                /* hasta que el producto del divisor supere al número p (así nos evitamos la raíz cuadrada).  */
         return 0;                                          /* Si la división da un residuo 0 quiere decir que ese número no es primo. Se regresa con 0.  */
   }
   return 1;                                                /* Si el algoritmo llega hasta aquí significa que el número es primo.                         */
}


Como ya viste C supongo que estás familiarizada con C entiendo que el operador de bit & te suena.

ruby

Muchas gracias por la respuesta, pero mi problema no es implementar el código en Java, sino interpretar ese código en C que me han dado y corregirlo. El programa que me han dado funciona mal, como he explicado, y tengo que hacer que funcione bien. El problema es que no entiendo algunas de las cosas que se hacen en la función es_primo y, por tanto, tampoco sé corregirlo para que funcione bien.

Alguien que me pueda explicar qué se intenta hacer en esa función por pasos? Gracias!

Serapis

Cita de: ruby en  3 Octubre 2021, 15:09 PM
...Alguien que me pueda explicar qué se intenta hacer en esa función por pasos?

El caso es que la explicación que solicitas se te da al comienzo, en los comentarios:
Citar
/*  Función es_primo (int p)
    p   parámetros de entrada. Número a evalurar si es primo
    Devuelve:
        0   Si p no es primo
        1   Si p es primo

    Para ver si un número es primo se intenta dividir por todos sus posibles divisores.
    Si alguno da resto cero, entonces no es primo
*/
Claro que es posible prestarse a confusión (cuando uno no lo entiende) si no se asocia a cada línea de código ...

Citarint es_primo ( int p )
   const int MAXFACTOR = ( int ) (sqrt ( (double)p )); /* Máximo factor posible de p */
En efecto, si por ejemplo buscas si 99 es primo, el máximo divisor de dicho valor será a lo sumo la raíz cuadrada (9*9), porque a partir de ese momento, el multiplicando va tomando los valores del multiplicador y al revés... que ya fueron comprobados. Es decir porque (a*b) = (b*a)

Citar
int f; /* Factor por el que se va comprobando si p es divisible */
   int primo; /* 1 Si p no es divisible por ningún f probado y 0 en caso contrario */
Quédate con que son dos enteros auxiliares en el cálculo y en vez de anticipar su uso, es preferible verlo (dado el caso), sobre la marcha cuando se usan.

Citar
   primo = ( ( p % 2 ) != 0 );
p es par o impar...?, se usará luego en el bucle en una forma embebida de condicional para el fin del bucle 'si primo=1' (si es impar)...

Citar
   for ( f = 3; primo && ( f > MAXFACTOR ); f = f + 2 )
El bucle comienza en 3 (nota que deja el 2 fuera del bucle, por la convenincia de saltar entre impares. Hay sin embargo un errror lógico ya que 2 es un número primo.
Como sabemos que el único primo par es el dos, se deduce que basta mirar los impares, toda vez que con solo el dividir entre 2 sabemos si es par y por tanto ya no es primo (si es superior a 2, verificación que falta).

Citar
      primo = ( ( p % f ) == 0 )
Similar a antes, pero ahora se pregunta si es p módulo f es par. Aquí se está diciendo que hay posibilidades de que sea primo, si al dividir 'p' entre 'f', el resto de la división no es 0 (condición que acabaría el bucle). Es decir si proporciona una división entera para este divisor, no es un primo pues tiene dos factores que lo dividen: 'f' y 'p/f'.

Citar
   return primo;
}
En los comentarios se indicaba que devolvía 0 si no era primo.

El código de Mafus, separa claramente cada caso, sin dejar fuera el 2... Y en el bucle, incluso aunque sea menos eficiente (una multiplicación que una comparación), queda más claro el límite del bucle que en el código que traes con MAXFACTOR... Nota la diferencia entre facilidad de entender y eficiencia de ejecución, para aprender interesa lo primero. Cuando funciona bien y se entiende al completo, puede optimizarse, al menos lo obvio.

Locura_23

Si vas a ver sistemas operativos te conviene hacer una buena repasadita a C  :rolleyes: