Foro de elhacker.net

#include <stdio.h>
#include <string.h>



//Declaramos nuestra función personalizada antes de usarla
//en main(). Esta es una buena práctica de programación en C,
//especialmente para que el compilador pueda verificar
//que los tipos de datos usados con los argumentos de la función sean correctos.
///
void EncontrarNumerosPrimosInferiores(int Limite_A_Inferiorizar);


int main(int argc, char **argv)
{
 int numero_limite=0;



 //'argc' es un argumento que puede estar en main(),
 //e indica cuántas opciones escribimos en la línea de comandos
 //del programa.
 //
 //'argc' siempre es 1 cuando se llama, por ejemplo, simplemente 'primos.exe'.
 //
 //pero si lo llamamos con algo como 'primos.exe 3133', 'argc' será 2 y
 //argv[1] contendrá la cadena "3133", que convertiremos a un entero.
 //
 ///
   if(argc<2)
   {
    printf("---------------------------------------------------\n");
    printf("Por favor use este programa con un numero. Ejemplo:\n");
    printf("     %s 31\n\n", argv[0]);
    printf("       En donde 31 puede ser cualquier otro numero entero\n");
    printf("       igual o mayor a 2.\n");
    printf("---------------------------------------------------\n\n");
    return 0;
   }


 //Convertir nuestra cadena numérica, pasada por la línea de comandos,
 //a un entero:
 ///
  numero_limite=atoi(argv[1]);


 //Si nuestro número límite es mayor o igual a 2, todo está bien.
 //De lo contrario, avisamos que el número especificado es un error:
 ///
  if(numero_limite>=2)
  {
     EncontrarNumerosPrimosInferiores(numero_limite);
  }
   else
   {
    printf("ERROR: El numero primo debe ser un entero mayor o igual a 2.\n\n");
   }


 //Volvemos al sistema:
 ///
  return 0;
}







void EncontrarNumerosPrimosInferiores(int Limite_A_Inferiorizar)
{
  //Aplicamos nuestro truco para encontrar solo los
  //primos menores al número dado:
  ///
   Limite_A_Inferiorizar=Limite_A_Inferiorizar-1;

  //Mantenemos un número actual que comprobar, a partir de 2:
  ///
    int numero_actual=2;


  //Necesitamos un número probador, que probará todos los números entre
  //2 hasta un número antes de nuestro numero_actual (es decir
  //mientras el numero_probador sea menor que numero_actual), y hace esto
  //para verificar que sea primo:
  ///
    int numero_probador=2;


  //Si este número no es 0, significa que el numero_actual no es primo
  //porque la división fue inexacta y dejó un residuo.
  ///
    int residuo_primos=-1;



  //Esto es para saber cuántos primos hay en total, menores
  //al numero_limite:
  ///
   int contador_primos=0;



  //Este es un bucle simple que se limita a buscar todos los
  //números primos directamente dentro del rango de 2 a numero_limite,
  //inclusive:
  ///
   while(numero_actual<=Limite_A_Inferiorizar)
   {
    //No hay ningún número par que sea primo, a excepción
    //de 2, así que esta línea lo que hace es ver si el
    //número actual es par, comparando con los pares originales
    //(2 y 0) para evitar tener que comprobar, y acelerar aún
    //más nuestro programa.
    //
    //Hacemos esto al aplicar una máscara AND a 'numeroprimo'
    //con el valor 3 (11 en binario) para quedarnos con los
    //2 bits de menor peso. Si esto es diferente de 2 o de 0,
    //solo puede ser 1 o 3, pero si es 2 o 0, el 'numeroprimo'
    //actual no puede ser primo.
    //
    //Esto es para descartar todos los números pares, ya que
    //sabemos que ningún número par a excepción de 2, es primo.
    ///
     if(numero_actual!=2 && (numero_actual&3 == 2 || numero_actual&3 == 0))continue;


    //Inicializar el residuo para determinar si el numero_actual
    //es primo. La inicializamos a -1 porque el bucle se detiene si
    //residuo_primos es 0; es decir, si no hubo residuo en una
    //operación, lo que significa que un número es exactamente divisible
    //entre otro:
    ///
     residuo_primos=-1;




    //Mientras que el bucle WHILE externo se preocupa de recorrer
    //cada número principal justo hasta numero_limite,
    //este bucle WHILE interno se preocupa de probar cada numero_actual
    //dividiéndolo entre cada numero_probador, que va desde 2 hasta
    //justo antes de numero_actual:
    ///
     while(numero_probador<numero_actual)
     {
      //Si encontramos una operación en la que el residuo fuera 0,
      //y ese número naturalmente no será sí mismo, porque estamos
      //comprobando solo menores a numero_actual en este bucle
      //interno, significa que este número no es primo:
      ///
      if(!(residuo_primos=numero_actual%numero_probador))
      {
//       printf("Detenido en %d %% %d\n", numero_actual, numero_probador);
       break;
      }

      //Probar si el numero_actual es primo, usando el siguiente
      //número de prueba:
      ///
       numero_probador++;
     }


      //Si el resudio para el numero_actual no es 0,
      //o si el numero_actual es 2, significa que nuestro
      //numero_actual es primo, DE ACUERDO A LA LÓGICA PARTICULAR DE ESTE PROGRAMA:
      ///
       if(residuo_primos || numero_actual==2)
       {
        //Mostramos el numero_actual, que es un primo:
        ///
         printf("%d\n",numero_actual);

        //Contabilizar que hemos encontrado un primo más:
        ///
         contador_primos++;
       }
     

    //Volvemos a inicializar nuestro número probador para la
    //siguiente repetición del bucle:
    ///
     numero_probador=2;


    //Avanzamos nuestro numero_actual para comprobar el
    //siguiente posible número primo:
    ///
     numero_actual++;
   }

 printf("Numeros primos menores a %d encontrados: %d", Limite_A_Inferiorizar+1, contador_primos);
}

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

int main (void)
{
 //Declaramos 5 variables enteras:
 ///
   int n,          //Para probar que cada número sea primo
       i,          //Para dividir cada número a comprobar con esta valor, de 2 hasta (numprimo/2)
       num,        //El valor introducido por el usuario
       numprimo=2, //El número a comprobar que va desde 2 hasta nuestro máximo
       t=0;        //Contador para mostrar cuántos números primos menores al máximo encontramos


 //Imprimir un mensaje pidiéndole al usuario que
 //escriba el número máximo deseado, para el que
 //debemos encontrar otros primos menores que este
 //(que no tienen matemáticamente nada que ver con el
 //número máximo... el número máximo es solo para decirle
 //al programa hasta antes de qué número, primo o no, buscar
 //primos):
 ///
  printf("Intruduzca un numero: ");


 //Leemos la entrada del usuario como un entero,
 //para lo que usamos la especificación de conversión
 //"%d" (así se le llama técnicamente a ese porciento
 //seguido de una letra). Esto es para que scanf convierta
 //automáticamente el valor, de una cadena de texto, a un
 //número entero.
 //
 //Guardaremos el valor leído en nuestra variable 'num'. Pero
 //ya que scanf necesita conocer la ubicación en memoria de la
 //variable, usamos el operador ampersand para pasarle
 //la dirección de memoria de esa variable en lugar de una copia
 //del valor que contiene.  Así, usamos '&num' (dirección de memoria)
 //en lugar de 'num' (simple copia de un valor numérico).
 //
 //Gracias a esto, scanf es capaz de colocar el valor entero
 //que convirtió a partir de la entrada de usuario (del número
 //máximo) exactamente en donde está nuestra variable 'num'
 //para que podamos usar este valor más adelante.
 ///
  scanf("%d",&num);









 //Un primo es un número entero positivo mayor a 1,
 //que solo puede dividirse exactamente por números
 //positivos enteros que son 1 y sí mismo.
 //Ya que no tomamos a 1 como primo, empezamos por 2
 //en la varible 'numprimo', con 'numprimo = 2'.
 //
 //'numprimo < num' signifca que el FOR se detendrá cuando
 //'numprimo' sea igual o mayor que 'num'.
 //
 // Esta parte también hace que si 'num' es menor a 2, o un
 // número negativo, no se procese nada, ya que esos son
 // números inválidos para buscar primos.
 //
 //Recordemos que 'num' es el valor que el usuario ingresó.
 //
 //
 //'numprimo++' significa que le sumaremos 1 a 'numprimo'
 //en cada repetición del FOR.
 //
 //Este primer bucle FOR, es el bucle externo, que se encarga
 //de imprimir cada número primo menor que el especificado, si
 //se determina que cada dicho número es realmente primo.
 //
 ///
   for (numprimo = 2; numprimo <num; numprimo++)
   {


     //Esta variable es para controlar el bucle interno:
     ///
      n=0;   //Esta variable es temporal para saber si 'i' es primo
      i=2;   //Nuevamente empezamos en 2 por la definición de los primos









       //Bucle interno WHILE:
       //Este bucle prueba cada número en i, desde 2 hasta lo
       //que el bucle FOR exterior tiene configurado como el
       //número a evaluar actualmente, en la variable 'numprimo'
       //
       //El 'numprimo/2' es una optimización matemática que podemos
       //usar con confianza y sin pensar mucho, pero que, hasta
       //donde recuerdo, dice que podemos determinar si un número
       //es primo o no, usando solamente la mitad de los números
       //que el número que estamos evaulando. Es en esos números
       //en los que se definirá si un número es primo o no, y una
       //de las razones es que en este rango encontramos números
       //más fundamentales, como 2, que ponen a prueba a cualquier
       //número.
       //
       //La intención de esto es que nuestro programa sea más rápido,
       //al aprovechar este hecho matemático que nos permite tener
       //que procesar solo la mitad de los números (y hay otras
       //optmizaciones matemáticas considerablemente más complejas).
       //
       //Al mismo tiempo, ya que estamos buscando primos menores que
       //el número que especificamos al comienzo, esto tiene el
       //potencial de descartar el número 2, si es ese nuestro número
       //máximo (aunque esto fue descartado en el bucle externo FOR).
       //
       //Por supuesto, esta optimización se hace para cada número
       //que vamos a imprimir, y no solo una vez. Así que si tenemos
       //que comprobar hasta 1003, necesitamos esta optimización para
       //(2/2), (3/2), (4/2), (5/2), (6/2), (7/2),
       //hasta llegar a (1003/2).
       //
       ///
        while (i <= numprimo/2)
        {
         //No hay ningún número par que sea primo, a excepción
         //de 2, así que esta línea lo que hace es ver si el
         //número actual es par, comparando con los pares originales
         //(2 y 0) para evitar tener que comprobar, y acelerar aún
         //más nuestro programa.
         //
         //Hacemos esto al aplicar una máscara AND a 'numeroprimo'
         //con el valor 3 (11 en binario) para quedarnos con los
         //2 bits de menor peso. Si esto es diferente de 2 o de 0,
         //solo puede ser 1 o 3, pero si es 2 o 0, el 'numeroprimo'
         //actual no puede ser primo.
         //
         //Ya que solo imprimimos números cuando 'n' es 0, para el
         //primer número en una serie, que es a partir de 2, siempre
         //se imprimirá este 2, si nuestro número máximo es mayor
         //a 2.
         ///
          if(numprimo&3 == 2 || numprimo&3 == 0)break;








          //Si el número actual, contenido en 'numprimo'
          //el cual termina justo en uno menor que el que
          //introdujimos al inicio; si este número actual
          //controlado por el bucle FOR externo tiene un
          //residuo de división de 0, al usar división o
          //módulo en este caso, entre 'i', que es controlado
          //por este bucle interno WHILE, guardamos el número
          //actual de 'i'.
          //
          ///
           if (numprimo % i == 0)
           {
            n=i;

            //Una vez que encontramos el primer número con una
            //división exacta entre 'numprimo' e 'i', podemos
            //detener este bucle interno WHILE:
            //
            ///
             break;
           }


           //Probamos el siguiente número. Eso significa que
           //'n' contendrá el último valor primo de la secuencia:
           ///
            i++;
        }




    //En el bucle interior WHILE anterior, probamos todos
    //los números hasta la mitad del camino.
    //Aumentamos 'i' en cada repetición del WHILE, y 'numprimo'
    //se mantiene en el mismo valor, a partir de 2, en todo el
    //proceso.
    //
    //Por ejemplo si nuestro número mayor es 4,
    //probamos dividir por:
    //
    //         numprimo % i == 2 % 2 == 0    (imprimimos 2)
    //         numprimo % i == 3 % 2 == 1
    //         numprimo % i == 3 % 3 == 0    (imprimimos 3)
    ///
     if (n == 0)
     {
      printf("\n\t%d\n",numprimo);
      t++;
     }
 }




 printf("Total de primos menores a %d: %d\n", num, t);


 //Función no estándar: sirve para hacer que
 //el sistema espere que el usuario
 //Presione una Tecla para Continuar...
 ///
  system("PAUSE");   



 //Devolvemos el control al sistema:
 ///
  return 0;
}

int EsUnPrimo( int MiNumero )
{
 int i=2;


 if     (MiNumero < 2)                 return 0;
 else if(MiNumero!=2 && MiNumero%2==0) return 0;
 else if(MiNumero == 2 || MiNumero==3) return 1;


 while( i < MiNumero/2+1 )
 {
  if( MiNumero % i == 0 ) return 0;
  i++;
 }


 return 1;
}

/*****************************************************************************


Versión "limpia", compacta, y un poco optimizada, de una función que determina
si un número individual dado, es primo o no.

http://devel.no-ip.org/

Este código es de dominio público (sin derechos de autor).
Puedes hacer lo que desees con él.


*****************************************************************************/

//Devuelve un valor diferente de 0 (o 1 específicamente aquí) si es primo;
//o devuelve 0 si no es primo:
//
///
 int EsUnPrimo( int MiNumero )
 {
  //Con esto comprobaremos los números, desde 2:
  ///
    int i=2;




  //Números menores a 2 no son primos:
  ///
   if(MiNumero < 2) return 0;
  



  //Después de comprobar el número sea positivo (y mayor o igual a 2)
  //con el IF inmediatamente arriba de esto, ahora esto es para descartar todos
  //los números positivos pares diferentes de 2, ya que sabemos que ningún número
  //par a excepción de 2, es primo. Con esto aceleramos nuestra función.
  ///
   else if(MiNumero!=2 && MiNumero%2==0) return 0;



  //2 y 3 son los únicos números que además de
  //ser primos, son demasiado pequeños para ser
  //tomados en cuenta por la optimización de la
  //división, así que los devolvemos estáticamente
  //como primos aquí:
  ///
   else if(MiNumero == 2 || MiNumero==3) return 1;





  //Solo la mitad de la secuencia de nuestro número es útil
  //para detectar si nuestro número, llamado 'MiNumero',
  //es primo:
  ///
    while( i < MiNumero/2+1 )
    {
     //Si dividimos exactamente por un número diferente
     //de 1 o de 'MiNumero', significa que el número
     //NO ES PRIMO, así que nos detenemos, devolviendo 0,
     //o FALSO:
     ///
      if( MiNumero % i == 0 ) return 0;


     //Si no detectamos nada especial,
     //pasamos al siguiente número de prueba:
     ///
       i++;
    }



   //Si llegamos aquí, significa que el número es primo,
   //así que devolvemos 1, o VERDADERO:
   ///
    return 1;
 }

/*****************************************************************************


Demostración DEPURADA Y UN POCO OPTIMIZADA de cómo encontrar
los primos menores a un número dado.

http://devel.no-ip.org/

Este código es de dominio público (sin derechos de autor).
Puedes hacer lo que desees con él.


*****************************************************************************/

#include <stdio.h>
#include <string.h>



//Declaramos nuestra función personalizada antes de usarla
//en main(). Esta es una buena práctica de programación en C,
//especialmente para que el compilador pueda verificar
//que los tipos de datos usados con los argumentos de la función sean correctos.
///
  void EncontrarNumerosPrimosInferiores(int Limite_A_Inferiorizar);





int main(int argc, char **argv)
{
 int numero_limite=0;



 //'argc' es un argumento que puede estar en main(),
 //e indica cuántas opciones escribimos en la línea de comandos
 //del programa.
 //
 //'argc' siempre es 1 cuando se llama, por ejemplo, simplemente 'primos.exe'.
 //
 //pero si lo llamamos con algo como 'primos.exe 3133', 'argc' será 2 y
 //argv[1] contendrá la cadena "3133", que convertiremos a un entero.
 //
 ///
   if(argc<2)
   {
    printf("---------------------------------------------------\n");
    printf("Por favor use este programa con un numero. Ejemplo:\n");
    printf("     %s 31\n\n", argv[0]);
    printf("       En donde 31 puede ser cualquier otro numero entero\n");
    printf("       igual o mayor a 2.\n");
    printf("---------------------------------------------------\n\n");
    return 0;
   }


 //Convertir nuestra cadena numérica, pasada por la línea de comandos,
 //a un entero:
 ///
  numero_limite=atoi(argv[1]);


 //Si nuestro número límite es mayor o igual a 2, todo está bien.
 //De lo contrario, avisamos que el número especificado es un error:
 ///
  if(numero_limite>=2)
  {
     EncontrarNumerosPrimosInferiores(numero_limite);
  }
   else
   {
    printf("ERROR: El numero primo debe ser un entero mayor o igual a 2.\n\n");
   }


 //Volvemos al sistema:
 ///
  return 0;
}







void EncontrarNumerosPrimosInferiores(int Limite_A_Inferiorizar)
{
  //Aplicamos nuestro truco para encontrar solo los
  //primos menores al número dado:
  ///
   Limite_A_Inferiorizar=Limite_A_Inferiorizar-1;

  //Mantenemos un número actual que comprobar, a partir de 2:
  ///
    int numero_actual=2;


  //Necesitamos un número probador, que probará todos los números entre
  //2 hasta un número antes de nuestro numero_actual (es decir
  //mientras el numero_probador sea menor que numero_actual), y hace esto
  //para verificar que sea primo:
  ///
    int numero_probador=2;


  //Si este número no es 0, significa que el numero_actual no es primo
  //porque la división fue inexacta y dejó un residuo.
  ///
    int residuo_primos=-1;



  //Esto es para saber cuántos primos hay en total, menores
  //al numero_limite:
  ///
   int contador_primos=0;


  //Este es un bucle simple que se limita a buscar todos los
  //números primos directamente dentro del rango de 2 a numero_limite,
  //inclusive:
  ///
   while(numero_actual<=Limite_A_Inferiorizar)
   {
    //No hay ningún número par que sea primo, a excepción
    //de 2, así que esta línea lo que hace es ver si el
    //número actual es par, comparando con el par original
    //(2) para evitar tener que comprobar, y acelerar aún
    //más nuestro programa.
    //
    //Esto es para descartar todos los números pares, ya que
    //sabemos que ningún número par a excepción de 2, es primo.
    ///
     if(numero_actual!=2 && numero_actual%2==0)
     {
      numero_actual++;
      continue;
     }


    //Inicializar el residuo para determinar si el numero_actual
    //es primo. La inicializamos a -1 porque el bucle interno se detiene si
    //residuo_primos es 0; es decir, si no hubo residuo en una
    //operación, lo que significa que un número es exactamente divisible
    //entre otro.
    //
    //Esto funciona apenas porque en el caso de los números primos
    //2 y 3, y al usar la optimización de división a la mitad, estos
    //dos números quedan sin ser abarcados por esa lógica, y serían
    //descartados, si no fuera por la salvedad de que residuo_primos
    //es inicializado constantemente a un valor diferente de 0
    //(en este caso -1, pero podría ser cualquier otro valor).
    //
    //Esa inicialización a un valor diferente de 0 es especialmente para
    //estos dos números, demasiado pequeños para ser tomados en cuenta
    //si dividimos el (numero_actual/2). En otras palabras, los números
    //2 y 3 son tan pequeños que el bucle interno no correrá, así que
    //nuestro programa tiene que estar predeterminadamente configurado
    //a buscar números desde 2, y tener un valor diferente de 0 mientras
    //el numero_actual es 2 y 3, de forma estática.
    //
    //Para todos los demás casos (comenzando con el no primo 4 y el primo 5),
    //residuos_primos se configura a un valor diferente de 0 si el numero_actual es primo;
    //o a 0 si el numero_actual no es primo:
    ///
     residuo_primos=-1;




    //Mientras que el bucle WHILE externo se preocupa de recorrer
    //cada número principal justo hasta numero_limite,
    //este bucle WHILE interno se preocupa de probar cada numero_actual
    //dividiéndolo entre cada numero_probador, que va desde 2 hasta
    //justo antes de numero_actual:
    //
    //
    //Aquí aplicamos la optimización por el hecho de que solo se
    //necesita comprobar con la mitad de la secuencia de números
    //que llevan al número actual (porque ninguno de los números
    //que son mayores a la mitad de la secuencia dividirá igualmente/uniformemente/exactamente
    //al número actual, así que son inútiles para saber si el número
    //actual es primo).
    //
    //Lo que hacemos es dividir, pero para optimizar para el CPU
    //usamos desplazamiento de bits a la derecha en 1 posición
    //(cada bit que desplazamos a la derecha en una variable entera
    //positiva, o sin signo, equivale a dividir entre 2, 4, 8, 16,
    //32, 64, 128 bits, si desplazamos 1, 2, 3, 4, 5, 6, 7 bits,
    //respectivamente --y desplazar al la izquierda equivale a
    //multiplicar por esas "potencias de 2"--). Esto es mucho más
    //rápido que una operación con el operador de división /, o con
    //el operador de módulo %.
    //
    //Luego le sumamos 1. Aunque parece ser opcional, tal vez sea
    //preferible en caso de existir, entre infinitos números, alguno
    //que necesite comprobar un número más, en la primera mitad, cuando esa división daría
    //un resultado fraccionario de 0.5, en caso de ser un impar, y que pudiera
    //dar la posibilidad de que ese número opcional decida si el número es
    //primo o no.
    //
    ///
     while(numero_probador < ((numero_actual>>1)+1))
     {
      //Si encontramos una operación en la que el residuo fuera 0,
      //y ese número naturalmente no será sí mismo, porque estamos
      //comprobando solo menores a numero_actual en este bucle
      //interno (de hecho solo hasta numero_actual/2),
      //significa que este número no es primo:
      ///
       residuo_primos=numero_actual%numero_probador;
       if(residuo_primos==0)
       {
//        printf("Detenido en %d %% %d\n", numero_actual, numero_probador);  /*DEBUG*/
        break;
       }

      //Prepararnos a probar si el numero_actual es primo, pasando ya al siguiente
      //número de prueba:
      ///
       numero_probador++;
     }


      //Si el resudio para el numero_actual no es 0,
      //significa que nuestro numero_actual es primo,
      //DE ACUERDO A LA LÓGICA PARTICULAR DE ESTE PROGRAMA:
      ///
       if(residuo_primos)
       {
        //Mostramos el numero_actual, que es un primo:
        ///
//         printf("numero_actual == %d; residuo_primos == %d\n", numero_actual, residuo_primos);  /*DEBUG*/
         printf("%d\n", numero_actual);

        //Contabilizar que hemos encontrado un primo más:
        ///
         contador_primos++;
       }
//        else                                                        ///////////////////////////////*DEBUG*/
//        {                                                                                         /*DEBUG*/
//         printf("{numero_actual == %d; residuo_primos == %d}\n", numero_actual, residuo_primos);  /*DEBUG*/
//        }                                                           ///////////////////////////////*DEBUG*/
     

    //Volvemos a inicializar nuestro número probador para la
    //siguiente repetición del bucle:
    ///
     numero_probador=2;


    //Avanzamos nuestro numero_actual para comprobar el
    //siguiente posible número primo:
    ///
     numero_actual++;
   }

 printf("Numeros primos menores a %d encontrados: %d", Limite_A_Inferiorizar+1, contador_primos);
}