esto es igual que entrenar cualquier parte de tu cuerpo... buscar ejercicios y hacerlos... tambien investigar como otros lo hacen y ver si tu puedes hacerlo mejor...
por lo menos un punto claro para mucha gente es cuando resuelven especialmente el problema de buscar numeros primos... supongamos saber si 100.000.007 es primo
mucha gente haría
bool es_primo(int numero){
int i;
for(i = 2; i < numero; i++){// desde 2 hasta numero -1
if(numero%i == 0){// si i es divisor de numero
return false; // no es primo
}
}
return true; // si no hay divisores es primo
}
para saber si es primo hubieras hecho 100.000.007 operaciones eso tomará unos segundos incluso en un buen procesador
pero si calculas (o investigas en wikipedia) te darás cuenta que el mayor numero posible divisor, de un numero es su raíz cuadrada... así que podemos hacer el ciclo mucho más corto
for(i = 2; i <= sqrt(numero); i++)
aquí solo harás 10.000 operaciones (wow el numero decreció muchisimo)
pero bien te dirá cualquier libro y sistema que evites usar sqrt a menos que sea necesario,porque es una operación lenta y pesada... entonces, como sacar la raíz de un numero sin sacar la raíz?... elevandolo, un cuadrado es un operación simple
for(i = 2; i*i <= numero; i++)
las mismas 10.000 operaciones, pero ahora será más rapido!
sin embargo... aún comparas todos los numeros pares como 4, 6, 8.... sabemos que si es multiplo de esos, era multiplo de 2... así que podríamos solo probar impares agregando una condicion inicial
bool es_primo(int numero){
int i;
for(i = 3; i*i <= numero; i+=2){// desde 2 hasta raíz del numero
if(numero%2==0){//si es par
return false;// no es primo
}
if(numero%i == 0){// si i es divisor de numero
return false; // no es primo
}
}
return true; // si no hay divisores es primo
}
aquí si es par, ni si quiera pasa por el ciclo... resolviendo para los pares instantaneamente y ahora para llegar a nuestro numero solo necesitamos probar 5.000 opciones
hasta aquí tienes una buena opción para dejar... pero como estamos locos
necesitamos ir más profundo
sabemos que al eliminar los pares, eliminabamos el 50% de las opciones... pero al eliminar los multiplos de 3, eliminamos otro 15% del total (no es 33% porque 1 de cada 2 multiplos de 3, es par... 3,
6,9,
12,15,
18) así que de 5000, iríamos a 3500...
pero veamos... tendríamos que hacer un if con %2 y %3 el ciclo debería empezar en 5 (el primer primo luego de 2 y 3.... y deberíamos probar para 7... luego, no vale la pena probar para 9 (porque es multiplo de 3, pero si para 11... tenemos un patron
a probar colocaré ? multiplos de 2 y 3, colocaré · (cada simbolo representa un numero, empezaré con 123 para que se vea y luego solo simbolos)
123·?·?···?·?···?·?···?·?···?·?···?·?
se ve el recorrido claro probar, saltar, probar, saltar 3 y repetir.... para no hacer un ciclo irregular sino directo, podríamos saltar 6 por vez y hacer 2 if por ciclo...
123·?·?···?·?···?·?···?·?···?·?···?·?
----i·····c·····c·····c·····c·····c···
dejando el codigo en
bool es_primo(int numero){
if(numero <= 3 && numero > 1){// todo numero menor a 3 y mayor a 1
return true; // es primo... si el uno no es primo
}
if(numero%2==0 || numero%3==0){//si es par o multiplo de 3
return false;// no es primo
}
int i;
for(i = 5; i*i <= numero; i+=6){// desde 5 hasta raíz del numero
if(numero%i== 0 || numero %(i+2)==0){
return false;//no es primo
}
}
return true; // si no hay divisores es primo
}
parece una locura... es un camino largo... pero así se aprende y cada vez aprendes a darle la vuelta a los codigos... aqí si el numero es primo solo tenemos que calcular 3500 posibilidades... si no, de antemano descartamos el 65% de las posibilidades... vale la pena ir más profundo? está en ti calcularlo, pero yo diría que no, porque la eficiencia obtenida es muy baja....