27 Febrero, 2020, 19:00 *
Bienvenido(a), Visitante. Por favor, ingresa o regístrate.
¿Perdiste tu email de activación?

Ingresar con nombre de usuario, contraseña y duración de la sesión
Noticias: Renovado el procedimiento de inserción de archivos GEOGEBRA en los mensajes.
 
 
Páginas: [1]   Ir Abajo
  Imprimir  
Autor Tema: Programa en C para detectar si un número es primo  (Leído 44140 veces)
0 Usuarios y 1 Visitante están viendo este tema.
xamo
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Femenino
España España

Mensajes: 373


Ver Perfil
« : 04 Febrero, 2013, 18:22 »

Buenas, he planteado el siguiente programa en C para averiguar si un número es o no primo. La cosa es, que no sé si está bien resuelto del todo, por eso lo pongo aquí con mis preguntillas  :lengua_afuera::

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
    int n, c, divisores;
   
    do{
        printf("Introduzca el numero a determinar si es o no primo:\n");
        scanf("%d",&n);
    }while(!(n>=0)); /*He incluido un bucle do-while, para que el programa comience cuando le den un numero estrictamente positivo */
   
    divisores = 0; /*inicializo el contador divisores a 0 */
   
    for(c=2; c<=n/2; c++) /*Divido hasta n/2, porque superior a n/2 no hay divisores (digo yo...) */
    if (n%c == 0) divisores++; /*Si el resto es cero, aumento en uno el contador divisores*/
   
    if (divisores >= 1) printf ("%d no es primo\n", n);
    else printf ("%d es primo\n",n);
   
    system("pause");
    return(0);
}


¿Es correcto que sólo considere hasta n/2 en el for?

Creía que me había dejado el caso de "1" fuera, pero al no entrar en el bucle, directamente me dirá que 1 es primo.

No sé si habrá alguna manera más elegante o eficiente de crearlo. Si os ocurre algo, decidmelo.  :sonrisa:

Ah, y para pasarlo a función ¿cómo sería? Debo pasarle una variable "n" que sea el número a considerar, y luego ya el interior es íntegro a lo que tengo en la función main, ¿no? ¿Y para que me devuelva si es primo o no, uso un 1 o un 0?  :indeciso:

Muchas gracias por leer y saludos.
En línea
Piockñec
Pleno*
*****

Karma: +1/-0
Desconectado Desconectado

Sexo: Masculino
France France

Mensajes: 1.259


Ver Perfil
« Respuesta #1 : 04 Febrero, 2013, 19:12 »

A todo lo que has planteado, mi respuesta sería sí :sonrisa:
Me ha parecido una maravilla el programa :guiño: Pero yo le añadiría, caso de que un usuario maligno introdujera el 432985723894752893450 (que bien sabes que no es primo :guiño: ), para evitar que el programa se tire toda la vida dividiendo, un "break" en el bucle for, esto es, otra condición aparte de la que impones al escribir c>=n/2 (que, por cierto, lo del n/2 me parece genial). Y eso sustituiría tu variable divisores :sonrisa:
Esto lo puedes hacer así:
Al principio del programa, defines la cabecera:

int zuprimoh{int n};

Y debajo del programa:

int zuprimoh{int n}
{
  int Salida=1, c;
 for(c=2; c<=n/2; c++) /*Divido hasta n/2, porque superior a n/2 no hay divisores (digo yo...) */
    {
     if (n%c == 0)
     {
          break; /*Esto detiene el bucle*/
          printf{"El %d numero no es primo", n};
          Salida--;
     }
}
if(Salida==1)
printf{"El numero %d ES primo :sonrisa:",n};
return Salida;
}

En el programa, cuando quieras usarlo, escribes como si de un printf se tratara:
int main()
{
int s;
s=zuprimoh(6);
printf("Si el siguiente numero es 0, es compuesto, y sino, es primoh: %d",s};
return 0;
}
Hace un año que no programo nada, así que no te puedo asegurar que me falte un %, un &, un ; un int, un etc etc etc. Pero la idea es esa :sonrisa: (yo era un crack programando, aunque no tengo un nivel avanzado, ni me acuerdo de nah. ¡Harme caso, zuprimoh! hahaha :cara_de_queso: )        
En línea
Abdulai
Moderador Global
Pleno*
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 2.301


Ver Perfil
« Respuesta #2 : 04 Febrero, 2013, 19:43 »

...
¿Es correcto que sólo considere hasta n/2 en el for?

Es incorrecto en términos de eficiencia, solamente tiene sentido hasta [texx]\sqrt{n}[/texx].
En línea
feriva
Pleno*
*****

Karma: +1/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 8.769



Ver Perfil
« Respuesta #3 : 05 Febrero, 2013, 08:34 »



¿Es correcto que sólo considere hasta n/2 en el for?



Hola. Tal como te dice Abdulai hay algo mejor que eso. Hay una cosa que cumplen los números primos, una de las pocas cosas de la que podemos estar seguros, y es que van apareciendo de menor a mayor y dan lugar a compuestos únicos por su producto.

 Hasta el [texx]7^2=49[/texx], por ejemplo, todos los compuestos por producto de 7 con primos mayores que 7, no están en ese tramo, son más grandes evidentemente, por lo que todos los compuestos de ese tramo estarán formados por 3 y/ó por 5 obligatoriamente, así que todos serán divisibles entre 3 y/ó entre 5: [texx] 3\cdot 7[/texx], [texx]5 \cdot 11[/texx]... en fin, todos ésos.

 Así pues, si un número es el compuesto [texx]aabbc[/texx], por caso, donde "a",  "b" y "c" son los primos  [texx]a<b<c[/texx] vamos a suponer, entonces

 su raíz cuadrada es [texx]ab\sqrt{c}[/texx], con lo que la parte entera no es divisible entre [texx]c^2[/texx], luego nos basta utilizar la parte entera de la raíz de [texx]aabbc[/texx] para comprobar su divisibilidad probando divisores; si es compuesto, también los será el número que estamos poniendo a prueba porque es le cuadrado de esa raíz,  si es primo, por lo dicho, también lo será el número original.

 En cuanto a la programación, si se tratara de probar la primalidad de un conjunto de naturales y no de un número aislado -aunque no estoy seguro porque no conozco mucho este lenguaje- quizá se pudiera lograr más eficiencia utilizando "while-case" para descartar previamente los pares habidos en un array.


 Saludos.

 
En línea

alex_cadiz
Nuevo
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 4


Ver Perfil
« Respuesta #4 : 05 Febrero, 2013, 12:26 »

Lo veo bien salvo que entre un 0 o un 1, porque interpreta que son primos.

Si quieres hacerlo como función puedes hacer lo mismo que tienes en el main pero en realidad no es necesario recorrer el bucle for entero "contando" cuántos divisores tiene, en cuanto encontremos un divisior de [texx]n[/texx] ya podemos salir de la función asegurando que no es primo. Quedaría algo así:

int primo (int n){
int i;

if(n<=1) return 0;
for(i=2;i<=sqrt(n);i++)
  if(n%i==0) return 0;

return 1;
}


Y ya en el main se llama a la función y dependiendo de si el resultado es 1 o 0 se imprime en pantalla si es primo o no, respectivamente.
En línea
xamo
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Femenino
España España

Mensajes: 373


Ver Perfil
« Respuesta #5 : 05 Febrero, 2013, 12:29 »

Muchas gracias a todos por contestar.

Y muchas gracias alex_cadiz por escribirme la función, así me ha quedado mucho más clara.  :sonrisa:

Saludos.
En línea
argentinator
Consultar la FIRMAPEDIA __________________________________________________________________________________________________________________
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 7.287

Vean mis posts activos en mi página personal


Ver Perfil WWW
« Respuesta #6 : 05 Febrero, 2013, 12:58 »

La función de alex_cadiz es agradablemente escueta.

Aún así les doy una sugerencia.
La función sqrt(n) exige bastantes recursos a la máquina,
y por la manera en que está escrita la función, ese cálculo se hace en cada iteración.

Eso no es necesario, se puede hacer el cálculo de sqrt(n) una sola vez, guardarlo en una variable, y luego utilizar ese valor, lo cual será más eficiente:

int sq = (int) (sqrt(n)); 

for (i=2; i <= sq; i++)

Y el resto se deja igual.

En línea

Piockñec
Pleno*
*****

Karma: +1/-0
Desconectado Desconectado

Sexo: Masculino
France France

Mensajes: 1.259


Ver Perfil
« Respuesta #7 : 05 Febrero, 2013, 13:20 »

Pues sí, esa función es una maravilla, ¡qué concisa! :sonrisa:
En línea
Páginas: [1]   Ir Arriba
  Imprimir  
 
Ir a:  

Impulsado por MySQL Impulsado por PHP Powered by SMF 1.1.4 | SMF © 2006, Simple Machines LLC XHTML 1.0 válido! CSS válido!