Quote:
|
Originariamente inviato da Manugal
come metto numeri un pò più grandi per trovare il numero perfetto ci mette un pò di più
|
Tieni conto del fatto che, quando verifichi se N è perfetto, devi fare O(N) verifiche di divisibilità... non mi stupisce che su numeri grandini ti ci voglia un bel
po' di tempo.
Quote:
Codice:
for(i=2; i<=n; ++i){
sum_div=0;
for(j=2; j<=i; ++j)
|
Nella definizione di numero perfetto, 1 è considerato un divisore.
Perciò, o fai il ciclo su j a partire da j=1, o inizializzi sum_div a 1 a ogni nuova iterazione su i.
Quote:
Codice:
if(i%j==0){
sum_div+=(i/j);
continue;
}
|
In realtà puoi aumentare di j, perché se a un'iterazione trovi il divisore j, a un'altra trovi il divisore i/j.
(A meno che non sia i=j^2, ma comunque quello va contato una volta sola.)
Quote:
Codice:
else continue;
if(sum_div==i){
printf("%d ", i);
|
Tu conti i divisori di i fino a i
incluso.
Quindi, quando hai finito, i è perfetto se e solo se sum_div è uguale a 2i.