Mejorar el codigo

[AprendiendoAProgramar]

Buenas.

Desarrolle un código para que me salieran los numeros primos de 1-100, aunque lo logré creo que mi código se puede mejorar mucho más para simplificarlo, ¿alguien podría ayudarme?

Código (cpp) [Seleccionar] Expandir

#include<iostream>
#include<conio.h>


using namespace std;

int main(){

    int contador,aux=1;

    for(int i=1;i<=100;i++){
        contador=0;
        aux=1;
        while(aux<=i){

            if(i%aux==0){
                contador++;
            }
            aux++;

        }
        if(contador==2){
            cout<<i<<endl;
        }
        if(i==1)cout<<"1"<<endl;

}

    getch();
    return 0;
}


[engel lex]

2 detalles sobre los numeros primos

1- nunca un par es primo, si no evaluas pares te ahorras el 50% del proceso
2- el minimo multiplo de un numero nunca es mayor que su raíz, es decir, si desglosamos 100

Código [Seleccionar] Expandir

1    2   4   5   10
100  50  25  20  10

el punto de confluencia siempre será su raiz, ya desde allí es la misma cuenta invertida, con esto et vas a ahorrar un monton de ciclos, por ejemplo para saber si 1.000.001 es primo solo es necesario probar hasta 1.000, así que son 1.000 ciclos (en este caso solo el 0.1% del trabajo y por ser raíz la eficiencia aumenta con lo grande del numero)... sin embargo calcular la raiz cuadrada es una operacion pesada y debemos velar que esto no consuma el proceso que nos ahorramos, así que lo calculamos en inversión...

por esto antes de hacer un programa es importante investigar todas las teorías y temas asociados...

estos 2 consejos son basicos... con esto para los primos de 1.000.001 solo necesitas 0.05% del trabajo que haría tu código

si metemos allí los multiplos de 3 nos reducimos 15% más y el codigo queda algo como

Código (cpp) [Seleccionar] Expandir

//nunca haremos primos de negativos y podemos evaluar  primos hasta de 64bit
bool es_primo(long unsigned int num){

 if(num <= 3){
   return >=2; //1 no es primo
 }

 long unsigned int mult;

 //si mult es la raiz, mult*mult debe ser el numero
 for(mult = 5;mult*mult < num; mult += 6){ //+=6 porque 6 es multiplo de 3 y 2
   if(num % mult == 0) {
     return false; // no es primo
   }
   if(num+2 % mult == 0) {
     return false; // no es primo
   }
 }
 return false; // llegados a este punto debe ser primo
}

lo hice de mente, espero no tenga errores

[Serapis]

Yo no lo haría de forma ligeramente diferente a como lo resuelve engel lex

Básicamente sabemos que solo tiene posibilidades de ser primo si acaba en 1,3,7 ó 9, luego esa debería ser la primera condición a verificar.
Luego, en efecto basta con llegar a la raíz cuadrada del número más alto, ya que a*b = b*a, con lo que al llegar al punto donde 'a' sea la raíz cuadrada, luego los valores de 'a', irán tomando los de 'b' y viceversa...

Código [Seleccionar] Expandir


buleano = funcion EsPrimo(entero Valor)
     entero unidades, max, k

    unidades = (valor modulo 10)

    Si ((unidades and 1) = 1) luego  // primer filtro  (eliminamos los acabados en 0,2,4,6 y 8, es decir aceptamos solo los impares
        Si (unidades = 5) luego   // y ahora descartamos el impar 5
            Si (valor=5) luego
                Devolver TRUE
            Sino
                Devolver FALSE  // cualquier otro múltiplo de 5 no es primo.
            Fin si
        Sino
            max = RaizCuadrada(valor) +1  // segundo filtro,
            bucle para k desde 7 hasta max en incrementos de 2
                  Si ((valor modulo k) = 0) Devolver FALSE
            Fin bucle

            Devolver TRUE
        Fin si
    Sino  // todavía podría ser 2 que es el único par que es primo (divisible sólo: por sí mismo y la unidad)
        Si (valor = 2) luego
            Devolver TRUE
        Sino
            Devolver FALSE
        Fin si
    Fin si
Fin funcion
Este código es óptimo para saber si un número cualquiera (aleatorio) es primo, pero si vas a operar con una lista seguida de valores, puede ser optimizada, toda vez que determinadas comprobaciones pueden moverse al bucle principal de la lista, evitando la llamada a esta función.

Aparte de eso, el bucle puede mejorarse toda vez que sabemos que si acaba en 5, no será primo, y también porque muchos impares son múltiplos de 3 (esto es cada 3 impares seguidos, 1 es múltiplo de 3): 11,13->15;  17,19->21; 23,25->27; 29,31->33 . 

Queda a tu esfuerzo optimizar dichos casos...

[MAFUS]

Para aligerar aún más las cosas (a expensas de usar más memoria) te diría que fueras guardando los primos encontrados en una lista dinámica y usaras los elementos de esa lista como divisores del número que estás operando. Si llegas al final de ella ( o superas la raíz cuadrada del número), sin que ningún elemento haya sido divisible por el número, has encontrado el siguiente primo y lo incluyes en la cola de la lista. Así te evitas de realizar muchas operaciones.

La razón de esto es que cuando factorizas, si te das cuenta, usas siempre el menor primo.

[CalgaryCorpus]

Otra manera de optimizar esta logica es modificando el ciclo propuesto que parte en 7 y que va de 2 en 2, haciaendo que sume 4 y luego sume 2 (alternadamente), saltandose posibles factores que se sabe no son primos.

7, (+4=) 11, (+2=) 13, (+4=) 17, (+2=) 19, (+4=) 23, (+2=) 25, (+4=) 29, (+2=) 31, ...

[engel lex]

Otra manera de optimizar esta logica es modificando el ciclo propuesto que parte en 7 y que va de 2 en 2, haciaendo que sume 4 y luego sume 2 (alternadamente), saltandose posibles factores que se sabe no son primos.

7, (+4=) 11, (+2=) 13, (+4=) 17, (+2=) 19, (+4=) 23, (+2=) 25, (+4=) 29, (+2=) 31, ...

justamente esto hago

de cabeza evalúa 2 y 3, de allí en más empieza en 5 y evalúa x y x+2, luego avanza 6 es decir va algo como 5;7, 11;13, 17;19, 23;25, 29;31, 37;43