Cita de: leosansan en 10 Agosto 2014, 09:13 AM
Eso último no está nada claro, si el número es 1 millón habría que probar según tu propuesta hasta num*num = 1000 000 , es decir de 3 a num=1000.
no entendí lo que no estaba claro D: pero extiendo
en lugar de probar de 2 en 2 desde 3 hasta 3.123.133 (dando unos 1,5millones de ciclos) se haría desde 3 durante i*i <= 3.123.133 siendo unos 884 ciclos si no me equivoco...
lo que tu dices de saltar todos los otros factores no me parece una buena idea, porque implicaría almacenar en memoria todos los factores intermedios y evaluarlos creando un ciclo secundario... siento que se haría un motón de operaciones de modulo extra en lugar de simplemente el modulo del numero que si falla es uno solo y listo...
o por lo menos que entendí de tí sería algo como esto...
Código (cpp) [Seleccionar]
for (i = 3; i * i <= valor; i += 2){
for ( primos[k] ; prims[k] * primos[k] <= n ; k++ ){
if ( n % primos[k] == 0 ) //ir con el siguiente i
}
//si no saltó almacenar i en arreglo
-----sigo agregando-----
la cantidad original de modulos a ejecutar era
n/2-3
yo lo indico llevar a
sqrt(n)/2-3
tu lo estás llevando a
(n-3)*k!
donde k es la cantidad de primos intermedios :s (ya que serían 2 ciclos haciendo mods y el segundo creciendo en cada vuelta de n)
incluso pensé hace tiempo que podría hacerse
Código (cpp) [Seleccionar]
for (i = 3; i * i <= valor; i += 2){
if(i%3==0) continue;
if(i%5==0) continue;
porque "aumenta" la eficiencia en ~20% pero no, ya que al final en el mejor de los casos hace 1 mod (si es multiplo de 3), y en el peor hace 3 mods, sabiendo que en este ciclo la operacion más pesada es el mod y es igual en tiempo para %3 y %3.000.000, entonces no vale la pena el procesamiento extra