[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!

[AnonimoVeneziano]

Originariamente inviato da 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!

Ehm cos'è un numero perfetto?

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

[Ziosilvio]

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.

    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]

Originariamente inviato da AnonimoVeneziano

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.

[repne scasb]

Originariamente inviato da Manugal

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

[Ziosilvio]

Originariamente inviato da Manugal

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?