Stavo cercando di trovare la somma dei divisori di numeri fino a 10 6 . I test case sono simili all'ordine di 10 5 . Ho fatto qualche pre-elaborazione come
int divisors(int num)
{
int sum=0;
for(int i=1; i*i<=num; i++)
sum += (num%i)? 0 : ((i*i==num)? i : i+num/i);
return sum;
}
C'è un metodo migliore per fare lo stesso. Dovrei anche creare una serie di numeri primi o qualcosa del genere?
Suggerimento. È più facile capire quanti numeri in un intervallo che, diciamo, 12 divideranno piuttosto che preoccuparsi di capire quali sono quelli che divide.
Questo ti dà un algoritmo O(n) che ti permette di calcolare la tua risposta in un tempo probabile accettabile per 10 6 .
Se lo desideri più velocemente, il suggerimento 2 è che devi farlo solo fino a n/2 - dopodiché hai solo bisogno della somma dei numeri, perché ognuno è un fattore una sola volta. Esiste una formula ben nota per la somma di tutti gli interi fino a 'n', che fornisce un cortocircuito. Ancora O(n) , ma un fattore migliore.
Per una maggiore rapidità, il suggerimento 3 è che devi farlo solo fino a n/3 - hai 2x la somma dell'intervallo da n/3 a n/2 e poi tutto l'intervallo da n/2 a %codice%. Stesso commento sulle prestazioni di prima.
Il suggerimento 4 è che mentre lo ripeti, c'è un modello più generale che puoi capire. Fallo bene e le prestazioni diventano n che è decisamente abbastanza veloce.
Leggi altre domande sui tag numbers optimization math