Autor Tema: Re: numeros primos (Leído 3047 veces)

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.

Astor

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.

GTow

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

GTow

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

Astor

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 ?

plaf

#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);
   }
}

plaf

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

GTow

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

JuanK

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

 
#include<stdio.h>
 
int main()
{
  int n,primo=0,cont=2;
 
  clrscr();
  printf("nDigite el numero a evaluar: ");
  scanf("%d",&n);
 
  if(n !=1 && n !=2 && n!=3)
  {
 
    while((cont <= (n/2)+1 ) &&  n%cont!=0)
      cont++;
    if(n%cont==0)
      printf("nEl numero NO es primo");
    else
      printf("nEl numero SI es primo");
  }
  else
    printf("nEl numero SI es primo");
  getch();
}
 
 

Suerte

Juank

Arsys

¿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

JuanK

usa esto

Código: Text

 
  while((cont <= (n/2)+1 ) &&  n%cont!=0)
    cont++;

dentro de otro ciclo que te vaya haciendo los incrementos de n.

Juank

GTow

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.

Arsys

¿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

JuanK

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

Arsys

Juank tu programa no funciona bien, el numero 3 es primo, sin embargo al introducirlo en tu programa dice que no es primo.

Saludos

JuanK

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

 
int main()
{
  int n,cont=2, primo=1;
 
  clrscr();
  printf("nDigite el numero a evaluar: ");
  scanf("%d",&n);
 
  if(n !=1 && n !=2 && n!=3)
  {
    while((cont <= (n/2)+1) && primo)
    {
      primo = n%cont;
      cont++;
    }
  }
  if(primo)
     printf("nEl numero SI es primo");
  else
     printf("nEl numero NO es primo");
  getch();
  return 1;
}
 
 

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