Salve a tutti,
Sto codificando un programma che deve essere
il più efficiente possibile e all'interno di questo programma devo trovare la somma dei divisori propri di un numero n (con n che va da un MAX, 1 milione, a 1). Ho trovato due metodi per fare ciò, il primo è questo:
int main(){
int n=MAX,i,sum;
while(n--){
for(i=2,sum=1;i<=sqrt(n);i++)
if(n%i == 0)
(i!=n/i)? sum+=i+(n/i) : sum+=i;
}
return 0;
}
e il secondo è questo:
int main(){
int n=MAX,app,div,esp,sum;
while(n--){
sum=1;
app=n;
div=2;
while (div<=app) {
esp=0;
if (app%div == 0){
while (app%div == 0){
esp++;
app /= div;
}
sum*=((pow(div,esp+1)-1)/(div-1));
}
else
div++;
}
sum-=n;
}
return 0;
}
Al momento sto lavorando sulla velocità di questi due programmi e non mi interessa usare la sum che calcolo (la userò poi nel programma completo in cui sfrutterò uno dei due algoritmi). Io credevo che con la fattorizzazione sarei stato molto più veloce e invece (al momento) non è così.
La domanda è, son io che non ho migliorato abbastanza l'algoritmo della fattorizzazione o è giusto e normale che sia più lento?
Ci tengo anche a precisare che programmo in C da circa due mesi, perciò qualsiasi consiglio (o 'trucco') per massimizzare l'efficienza di un programma (e per programmare meglio) è ovviamente ben accetto!
Questo è la prima discussione che apro su questo Forum, perciò spero di aver fatto tutto correttamente.
Grazie in anticipo, e buone feste!