codigo para calcular los numeros primos

[minari02]

Hola que tal, he empezado con C++ hace poco, hay un ejercicio bastante concurrido cuando se esta estudiando programación y es de imprimir en pantalla números con ciertos rangos, uno de ellos es el de los números primos, creo que un no soy capaz por decirlo asi de poder programar dicho codigo, buscando, me he encontrado este código

Código [Seleccionar] Expandir


#define LIMITE 35000
int main ()
{
   int i, j, primo, num;
   printf ("Introduzca numero: ");
   scanf ("%d", &num);
   i = num + 1;
   do
   {
      primo = 1;
      for (j = 2; j <= i/2 && primo; j++)
         if((i%j) == 0)
            primo = 0; 
      if (primo)
         printf("%d\n", i);   
      i++;   
   }while ( i < LIMITE && !primo);
   system("pause");
   return 0;
}


he intentado entenderlo pero hay algunas cosas que aun no comprendo, son pequeñas cosas, asi que desearía saber si por favor me ayudarían a comprenderlo, poniendo como comentario como funciona cada linea, bueno los temas que he visto son: funciones de entrada(con libreria stdio y iostream),tipos de datos,if y else,operadores logicos, ciclo while, ciclo for(hoy) todo de una manera superficial, que opinan ya deberia saber hacerlo?

Gracias.

pd: he visto que algunos se molestan con algunas preguntas algo asi... por que son preguntas talvez de tareas o similares, sin embargo... estén sin cuidado, yo ya he terminado el colegio y pues.. esto es solo algo que me apasiona y ps deseo aprenderlo aun por mi propia cuenta.jaja

Saludos. Feliz Navidad jeje...       

[ivancea96]

Código (cpp) [Seleccionar] Expandir

#define LIMITE 35000
int main ()
{
   int i, j, primo, num;
   printf ("Introduzca numero: ");
   scanf ("%d", &num);
   i = num + 1;
   do
   {
      primo = 1;
      for (j = 2; j <= i/2 && primo; j++) //Pasamos por todos los números hasta i/2
         if((i%j) == 0) //Si se encuentra un divisor (i/j -> resto==0) se pone que primo es = a 0
            primo = 0;
      if (primo) //Si es primo, lo escribe
         printf("%d\n", i);   
      i++;    //Aumenta 'i', para ir al siguiente número
   }while ( i < LIMITE && !primo);
   system("pause");
   return 0;
}


Sencillamente, mira todos los números, desde 2 hasta la mitad del número, para ver si alguno es divisor. Si alguno lo es, resulta que no es primo, y primo = 0.

El programa mira el primer número superior al número que tú le introduces.

Acerca de lo de i/2, es porque, si no es divisible por 2, tampoco es divisible por su mitad. Así se ahorra mucho tiempo en números grandes.

[minari02]

Hola amigo, gracias por tu respuesta  , me podrias expricar para que sirve el %? no lo habia visto asi, solo %d, %c, f%

[ivancea96]

5/2, en números enteros, da de resultado 2.
5%2, en números enteros, da de resultado 1.

% da el resto de una operación.

[minari02]

mm.. amigo me podria decir que significa esta linea

Código [Seleccionar] Expandir

printf("%4d",1); creo que es muy importante, trate de cambiarla para entender mejor como funciona cada parte del programa y pues... simplemente sale un error es asi :

Código [Seleccionar] Expandir

floating point exception (core dumped) y pues... estuve buscando pero no se como se llama y no pude encontrar info sobre ello.

Gracias.

[leosansan]

Respuesta en que_significa_y_como_se_llama_printf4d1_en_c

No dupliques los temas, ya lo habías preguntado aquí. Espera que te contesten en lugar de abrir un nuevo tema con la misma pregunta que en este  tema.


Felices Navidades y Próspero Año Nuevo.

Saluditos! ..... !!!!

[amchacon]

Sencillamente, mira todos los números, desde 2 hasta la mitad del número

En realidad sería hasta la raiz del número.

Ponte el caso con 36, el máximo divisor aquí es 6 (lo que viene a ser 6x6). Cualquier número que encuentres superior a eso 12 (12x3) no será nada más que el inverso de uno anterior (3x12).

También podríamos generarnos una tabla booleana diciendo cual es primo y cual no. Usando la criba de eratostenes (mira el gif):
http://es.wikipedia.org/wiki/Criba_de_Erat%C3%B3stenes

[leosansan]

En realidad sería hasta la raiz del número.

El caso es si sabe donde se pone la raíz cuadrada. Y no olvidarse de incluir la librería math.h.

También podríamos generarnos una tabla booleana diciendo cual es primo y cual no. Usando la criba de eratostenes (mira el gif):
http://es.wikipedia.org/wiki/Criba_de_Erat%C3%B3stenes

A mi modesto entender, ello implica calcular y guardar en arrays los sucesivos múltiplos de 2,3,5, etc para posteriormente por comparación comprobar que no está en ellos. A mí por lo menos me ha dado una pobre eficiencia, supongo que debido al cambio de calcular si un módulo es cero por el tener que rellenar arrays y posteriormente comparar. Igual tu lo tienes más optimizado.

Una pequeña mejora, además de lo de la raíz, es ir comprobando sólo los impares, ya que sabemos que los pares, excepto el 2, no son primos:

Código (cpp) [Seleccionar] Expandir


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

int main()
{
    int n,i,j,rq;
    printf("Introduce el numero por favor: ");
    fflush (stdout);
    scanf("%d",&n);
    if (n==1){
        printf("2");
        return 1;
    }
    printf("2");
    fflush (stdout);
    for (i = 3;i <= n;i+=2){

        j = 3;
        while (j <= rq && i % j != 0)
            j++;
        if (i == j){
            printf("%4d",j);
            fflush (stdout);
        }
    }
    return 0;
}


No es el más efiiciente pero no quería cambiarle sustancialmente su código.

Felices Navidades y Próspero Año Nuevo.

Saluditos! ..... !!!!

[ivancea96]

Leosansan, no estableces en ningún momento el valor de la variable "rq".

Código (cpp) [Seleccionar] Expandir


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

int main()
{
    int n,i,j,rq;
    printf("Introduce el numero por favor: ");
    fflush (stdout);
    scanf("%d",&n);
    if (n==1){
        printf("2");
        return 1;
    }
    printf("2");
    fflush (stdout);
    for (i = 3;i <= n;i+=2){
        rq = sqrt(i);
        j = 3;
        while (j <= rq && i % j != 0)
            j++;
        if (i == j){
            printf("%4d",j);
            fflush (stdout);
        }
    }
    return 0;
}

[amchacon]

El caso es si sabe donde se pone la raíz cuadrada. Y no olvidarse de incluir la librería math.h.

No hace falta usar la librería math.h, estamos hablando de la raiz entera:

Código (c) [Seleccionar] Expandir

for (i = 2; (i*i) <= n;i++)

A mi modesto entender, ello implica calcular y guardar en arrays los sucesivos múltiplos de 2,3,5, etc para posteriormente por comparación comprobar que no está en ellos. A mí por lo menos me ha dado una pobre eficiencia, supongo que debido al cambio de calcular si un módulo es cero por el tener que rellenar arrays y posteriormente comparar. Igual tu lo tienes más optimizado.

No guardo los primos, sino todos los numeros naturales hasta N. Te dejo aquí el código:

Código (c) [Seleccionar] Expandir

#include <stdio.h>
#define PRIMO 1
#define COMPUESTO 0
#define NO_DEFINIDO -1

const int MAX = 120;

void tacharMultiplos(char Tabla[],int N)
{
   int i;
   for (i = 2;(N*i) <= MAX;i++)
   {
       Tabla[N*i] = COMPUESTO;
   }
}

void mostrarTabla(char Tabla[])
{
   int i = 2;
   for (; i <= MAX;i++)
       if (Tabla[i] == PRIMO) printf("%d\n",i);
}

int main()
{
   // Generar Criba de erastotenes

   char Tabla[MAX+1]; // tabla booleana
   int i = 0;

   // valor inicial

   for (; i<= MAX;i++) Tabla[i] = NO_DEFINIDO;

   for (i = 2;i<=MAX;i++)
   {
       if (Tabla[i] == NO_DEFINIDO) // si no esta inicializada...
       {
           Tabla[i] = PRIMO;
           tacharMultiplos(Tabla,i);
       }
   }

   mostrarTabla(Tabla);
   return 0;
}

Si haces una solo comprobación no te sale rentable, pero si vas a hacer muchas comprobaciones te puede venir bien generarte esa tabla. De esa forma, cualquier comprobación que necesites hacer la puedes sacar instantaneamente para cualquier número <= MAX:

Código (c) [Seleccionar] Expandir

scanf("%d",&numero);
if (numero < max)
{
 if (Tabla[numero]) puts("Es primo");
 else puts("Es compuesto");
}
else
{
 if (esPrimo(numero)) puts("Es primo");
 else puts("Es compuesto");
}