[C] Numeri perfetti

[Manugal]

Ciao a tutti!!! :)

Ho un problema da risolvere ed è il seguente:

Scrivere un programma che dato in input un intero n, restituisce tutti i numeri perfetti fino n

Io ho provato a farlo, volevo sapere se andavo bene, perché come metto numeri un pò più grandi per trovare il numero perfetto ci mette un pò di più:



#include <stdio.h>

int main(void){

int n,i,j, sum_div;

printf("Inserisci un numero maggiore di 2: ");
scanf("%d", &n);

for(i=2; i<=n; ++i){
sum_div=0;
for(j=2; j<=i; ++j)
if(i%j==0){
sum_div+=(i/j);
continue;
}
else continue;
if(sum_div==i){
printf("%d ", i);
continue;
}
else continue;
}

return 0;
}



Grazie! :D

[AnonimoVeneziano]

Ciao a tutti!!! :)

Ho un problema da risolvere ed è il seguente:

Scrivere un programma che dato in input un intero n, restituisce tutti i numeri perfetti fino n

Io ho provato a farlo, volevo sapere se andavo bene, perché come metto numeri un pò più grandi per trovare il numero perfetto ci mette un pò di più:



#include <stdio.h>

int main(void){

int n,i,j, sum_div;

printf("Inserisci un numero maggiore di 2: ");
scanf("%d", &n);

for(i=2; i<=n; ++i){
sum_div=0;
for(j=2; j<=i; ++j)
if(i%j==0){
sum_div+=(i/j);
continue;
}
else continue;
if(sum_div==i){
printf("%d ", i);
continue;
}
else continue;
}

return 0;
}



Grazie! :D

Ehm cos'è un numero perfetto? :stordita:

Io sapevo che era il 3 il numero perfetto, no? :Prrr:

[Ziosilvio]

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.
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.
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.)
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.

[Ziosilvio]

cos'è un numero perfetto?
Un numero N>1 si dice perfetto, se è uguale alla somma di tutti i suoi divisori, incluso 1 ed escluso N.
Un numero pari è perfetto se e solo se ha la forma (2^(n-1))((2^n)-1) con (2^n)-1 primo: quindi 6=(2^(2-1))((2^2)-1) è primo, e così anche 28=(2^(3-1))((2^3)-1), ma non 120=(2^(4-1))((2^4)-1).
Non si conoscono numeri perfetti dispari, né si sa se ne esistano. Si sa però che, se esistessero, avrebbero almeno 300 cifre decimali.

Fonte: Wikipedia (http://en.wikipedia.org/wiki/Perfect_number).

[repne scasb]

Io ho provato a farlo, volevo sapere se andavo bene, perché come metto numeri un pò più grandi per trovare il numero perfetto ci mette un pò di più:


Se e' la prestazione che cerchi:


#include <stdio.h>

void main(void){

unsigned long i,j,k,l,m,n;

printf("Inserisci un numero maggiore di 2: ");
scanf("%ld", &n);

for(i=2;(j=(1L<<(i-1))*((1L<<i)-1))<=n;i++)
{
for(m=0,l=(1L<<i)-1,k=2;k*k<=j;k+=k==2?1:2)
{
if((l%k)==0)
{
m=1;
break;
}
}
if(m==0)
printf("%ld ",j);
}
}


NOTA: Potrebbero esserci degli errori l'ho scritta di getto in pochi minuti ed e' scarsamente ottimizzata.

[AnonimoVeneziano]

Grazie per la spiegazione Ziosilvio! :)

[Manugal]

Grazie delle risposte, però mi sembra molto strano che un numero N è perfetto se e solo se la somma di tutti i suoi divisori tranne N danno esattamente il numero N. Ad esempio considero il numero 6 (che è il più semplice numero perfetto). Secondo quello che ho pensato io faccio 6/2 (primo divisore) e viene 3 poi 6/3 (secondo divisore) e viene 2 e poi 6/6 (terzo divisore) e viene 1. Sommandoli viene esattamente 6. Se facessi come dite voi, innanzitutto se considero anche 1 come divisore già sono fuori con la somma (ma mettiamo il caso che non lo consideri), se io non considero poi, nel caso di 6, il 6 stesso come divisore, la somma dei divisori mi viene 5 e non 6 quindi non sarebbe più numero perfetto. Spero di essere stato chiaro. :)

[Manugal]

up

[VegetaSSJ5]

quando in un thread interviene Ziosilvio mi sento umiliato...
quando in un thread interviene repne scasb mi sento avvilito...
quanto intervengono entrambi mi viene voglia di suicidarmi... :cry: :muro: :bsod:

[Ziosilvio]

mi sembra molto strano che un numero N è perfetto se e solo se la somma di tutti i suoi divisori tranne N danno esattamente il numero N. Ad esempio considero il numero 6 (che è il più semplice numero perfetto). Secondo quello che ho pensato io faccio 6/2 (primo divisore) e viene 3 poi 6/3 (secondo divisore) e viene 2 e poi 6/6 (terzo divisore) e viene 1. Sommandoli viene esattamente 6.
Uhm... tu così non stai facendo la somma dei divisori, ma quella dei quozienti.
Infatti, quando j divide i, allora tu incrementi la somma non di j, ma di i/j.

Però --- ed è una cosa che, mea culpa, non avevo notato subito --- i divisori sono in corrispondenza uno-a-uno con i quozienti, e al divisore i corrisponde proprio il quoziente 1.
Inoltre, ci vuole poco a notare che anche i quozienti sono divisori, e i divisori quozienti.

Perciò, ripensandoci... mi sa che il tuo programma iniziale andava già bene.

[Manugal]

Ah ecco ora ho capito.. :) Ho fatto confusione tra quoziente e divisore, io infatti calcolo il quoziente e sommo il quoziente. Grazie.

[Manugal]

Scusate ma ancora non ho capito bene. Nell'ultimo passaggio mi hai detto che io aumento la somma di i/j, ma così sommerei i quozienti non i divisori come dovrei invece fare.. quindi in teoria il mio prog sarebbe errato? O no?