SoloCodigo

Programación General => C/C++ => Mensaje iniciado por: essios en Sábado 23 de Agosto de 2003, 14:16

Título: Re: numeros primos
Publicado por: essios en Sábado 23 de Agosto de 2003, 14:16
hola a todos. ya llevaba algun tiempo sin pasar por aqui.

a ver si alguien me echa un cable.

en realidad es un simple algoritmo. me indica si es primo o no, asi de facil.

la verdad es k a estas alturas hasta me da vergüenza preguntar estas cosas, pero para eso estamos, pa aprender.

saludos a todos.
Título: Re: numeros primos
Publicado por: Astor en Sábado 23 de Agosto de 2003, 15:39
Mira utilizando metodos convencionales no deberias tener problemas. Cuando es un numero primo ?...

Basta con que hagas un bucle desde 2 hasta n-1. Si encontras alguna division con resto 0, el numero no es primo. Si salis del bucle y nadie pudo dividirlo en forma entera -> el numero es primo.
Título: Re: numeros primos
Publicado por: GTow en Sábado 23 de Agosto de 2003, 19:28
Bueno, un matiz, si quieres ganar algo de velocidad te diré que no tienes que mirar hasta n-1, sino hasta la raiz cuadrada del numero (o el anterior si ésta no es exacta).
No sé si me explico, por ejemplo si el numero es el 10, solo tienes
Título: Re: numeros primos
Publicado por: GTow en Sábado 23 de Agosto de 2003, 19:29
Bueno, un matiz, si quieres ganar algo de velocidad te diré que no tienes que mirar hasta n-1, sino hasta la raiz cuadrada del numero (o el anterior si ésta no es exacta).
No sé si me explico, por ejemplo si el numero es el 10, solo tienes  que mirar hasta el 3, y efectivamente antes está el 2, asi que te dará resto cero y no será primo
Si fuera 11, como ni el 2 ni el 3 dan 0 pues si es primo. Ves que te ahorras operaciones en orden cuadrático -> Muchas más velocidad.
Siento q esté 2 veces, le he dado sin querer
Título: Re: numeros primos
Publicado por: Astor en Domingo 24 de Agosto de 2003, 01:58
Me podrias explicar el metodo un poco mas detallado, porque la verdad no comprendo que es lo que realmente terminas evaluando para saber si un numero es o no primo.
Podrias, si no es mucha molestia, explicarme nuevamente el ejemplo con 10 y 11 ?
Título: Re: numeros primos
Publicado por: plaf en Domingo 24 de Agosto de 2003, 04:33
#include<stdio.h>
#include<math.h>

int main(){
   int i,esprimo;
   float numero, div;
   while(1){
   printf("nnTengo hambre, dame un numero: ");
   scanf("%f",&numero);
   esprimo=1;
   for(i=2; i <= sqrt(numero) && esprimo; i++)
   {
      div=numero/(float)i;
      if(div-(int)div==0) esprimo=0;
   }
   if(esprimo) printf("Gracias, estaba muy primo es numero:)");
   else printf("PUAJ!! ESTE NUMERO ES DIVISIBLE POR %d!!!",i-1);
   }
}
Título: Re: numeros primos
Publicado por: plaf en Domingo 24 de Agosto de 2003, 04:51
de hecho podrias hacerlo el doble de eficiente haciendolo saltarse los pares (probar con 2 y despues empezar el for en 3 saltando de 2 en 2). y no se, empieza a probar lo q se te ocurra
Título: Re: numeros primos
Publicado por: GTow en Domingo 24 de Agosto de 2003, 13:55
Creo que con el Ejemplo que te han puesto ya no hace falta que te especifique más, PERO, saca la raiz del bucle, que sinó en caso de que el número sea grande vas a repetir la misma operación muchas veces, y si nos ponemos con la eficiencia...., pues eso. En cualquier caso si necesitas más explicación dilo
Título: Re: numeros primos
Publicado por: JuanK en Lunes 25 de Agosto de 2003, 14:10
Bueno, este es el que uso actualmente, y creo que esta bastante optimizado, sin embargo si se puede más me cuentan, si alguien no lo entiende me avisa y lo explico, no es dificil, pero de primera impresion podria serlo.

 
Código: Text
  1.  
  2. #include<stdio.h>
  3.  
  4. int main()
  5. {
  6.   int n,primo=0,cont=2;
  7.  
  8.   clrscr();
  9.   printf("nDigite el numero a evaluar: ");
  10.   scanf("%d",&n);
  11.  
  12.   if(n !=1 && n !=2 && n!=3)
  13.   {
  14.  
  15.     while((cont <= (n/2)+1 ) &&  n%cont!=0)
  16.       cont++;
  17.     if(n%cont==0)
  18.       printf("nEl numero NO es primo");
  19.     else
  20.       printf("nEl numero SI es primo");
  21.   }
  22.   else
  23.     printf("nEl numero SI es primo");
  24.   getch();
  25. }
  26.  
  27.  

Suerte

Juank
Título: Re: numeros primos
Publicado por: Arsys en Miércoles 27 de Agosto de 2003, 15:04
¿Como se haría para encontrar los numeros primos dentro de un intervalo de numeros?

Por ejemplo, para saber los numeros primos del 1 al 100.

Saludos :hippi:
Título: Re: numeros primos
Publicado por: JuanK en Miércoles 27 de Agosto de 2003, 16:53
usa esto
 
Código: Text
  1.  
  2.   while((cont <= (n/2)+1 ) &&  n%cont!=0)
  3.     cont++;
  4.  
  5.  
dentro de otro ciclo que te vaya haciendo los incrementos de n.

Juank
Título: Re: numeros primos
Publicado por: GTow en Jueves 28 de Agosto de 2003, 12:05
Juank, puede ser que no haya entendido bien tu programa, pero creo que miras hasta la mitad del número. En cambio, como ya expliqué anteriormente se puede hacer hasta la raiz cuadrada de éste, con lo que te ahorras muchísimo. :guitar:
Título: Re: numeros primos
Publicado por: Arsys en Jueves 28 de Agosto de 2003, 15:37
¿El 3 no es un número primo?

¿No son números primos aquellos que solo son divisibles entre si mismos para que su resto de 0?

Saludos :hippi:
Título: Re: numeros primos
Publicado por: JuanK en Jueves 28 de Agosto de 2003, 15:40
si so , es porque lo dices?
por lo de la raiz...? si es por eso yo tambien tengo mis dudas. pero tengo que revisar

Juank
Título: Re: numeros primos
Publicado por: Arsys en Jueves 28 de Agosto de 2003, 16:19
Juank tu programa no funciona bien, el numero 3 es primo, sin embargo al introducirlo en tu programa dice que no es primo.

Saludos :hippi:
Título: numeros primos
Publicado por: JuanK en Jueves 28 de Agosto de 2003, 17:58
Si, como de costumbre...
lo que pasa es que cuando escribo codigos pequeños, lo escribo de una vez sin compilar ni nada, por eso se me olvido colocar las 3 excepciones clasicas: 1  2  3.

En todo caso ya lo arregle y aca pego un codigo más optimizado:
 
Código: Text
  1.  
  2. int main()
  3. {
  4.   int n,cont=2, primo=1;
  5.  
  6.   clrscr();
  7.   printf("nDigite el numero a evaluar: ");
  8.   scanf("%d",&n);
  9.  
  10.   if(n !=1 && n !=2 && n!=3)
  11.   {
  12.     while((cont <= (n/2)+1) && primo)
  13.     {
  14.       primo = n%cont;
  15.       cont++;
  16.     }
  17.   }
  18.   if(primo)
  19.      printf("nEl numero SI es primo");
  20.   else
  21.      printf("nEl numero NO es primo");
  22.   getch();
  23.   return 1;
  24. }
  25.  
  26.  

Queda pendiente medir el tiempo de lo de la raiz cuadrada , porque no me convence que sea mas rapido, tampoco he mirado si funciona.

Juank