RISOLTO Trovare i numeri perfetti in C

[Emi02]

Ciao a tutti, sto cercando di risolvere un esercizio che richiede di trovare tutti i numeri perfetti da 1 a 1000 (si dicono tali quando la somma di tutti i fattori positivi è uguale al numero di partenza escludendo il numero stesso) tramite una funzione che deve essere definita da me. Il mio problema è che mi esce 24 e non dovrebbe comparire.
Grazie per tutte le risposte ragazzi, ps sto imparando da autodidatta quindi se vi sembra che io abbia dei vizi/mancanze da correggere fatemelo sapere.
Il codice è questo:

#include <stdio.h>

int perfect(int k, int x);


int main()
{
    puts("Di seguito verranno stampati tutti i numeri perfetti da 1 a 1000");
   for (int i = 1; i<=1000;i++) //tramite un for andiamo a testare tutti i numeri fino a 1000
   {
       int sum = 0;
       for (int j = 1; j <= i; j++)//j individua il divisore
       {
           sum += perfect(i, j);
           if (sum == i) printf_s("%d\n", i);
       }
   }
}

int perfect(int k, int x)//la funzione calcola i fattori dei numeri i progressivi
{
            int f = k % x;
            if (f == 0) return x;
            else return 0;
}

 

[BAT]

si dicono tali quando la somma di tutti i fattori positivi è uguale al numero di partenza

no, un intero è perfetto quando la somma dei suoi divisori (eccetto se stesso) è uguale al numero stesso, non è da confondere coi fattori (sottinteso: primi) del numero.
Esempio: il primo numero perfetto è il 6 perché 1+2+3=6 (1,2,3 divisori di 6)
il secondo n. perfetto è 28 perché la somma dei suoi divisori è 1+2+4+7+14=28

la funzione perfect che hai scritto è errata, è li dentro che devi sommare i divisori (inizializza la somma a 1 perché 1 è divisore di ogni numero ed inizia il controllo sui divisori a partire dal 2)
quindi un modo molto banale di farla è un ciclo che trova i divisori e li somma in una variabile interna, puoi fare il ciclo o incrementando il divisori dei 1 ogni volta o, dato che si può dimostrare che i numeri perfetti sono solo pari, la prima cosa che la funzione dovrebbe fare è controllare se il numero è dispari e in quel caso restituire false/0;
la funzione puoi migliorarla ulteriormente in quanto ogni volta che trovi un divisore in realtà ne trovi 2, perché se a:b=q (senza resto) allora sia b che q sono divisori di a (infatti se a:b=q ovviamente a:q=b)
il mio consiglio è mettere un limite al divisore massimo (inizialmente sarà a/2), se trovi un divisore maggiore di 2 lo abbassi (per ess se 3 è un divisore, allora a/3 sarà il nuovo limite massimo), questo ti permetterà di abbassare in modo drastico i tempi di calcolo
tra l'altro l'IF che controlla il risultato devi farlo fuori dal ciclo for, non dentro, altrimenti potresti avere dei falsi positivi

Una cosa diversa è la generazione dei perfetti, nel qual caso va usata un'altra proprietà su cui non mi dilungo perchè non è lo scopo dell'esercizio

 

[Eren88]

Cosi funziona:

#include <stdio.h>
#include <stdlib.h>

int perfect(int k, int x);

int main()
{
    printf("Di seguito verranno stampati tutti i numeri perfetti da 1 a 1000\n");
    for (int i = 1; i <= 1000; i++) { //tramite un for andiamo a testare tutti i numeri fino a 1000
        int sum = 0;
        for (int j = 1; j < i; j++) { //j individua il divisore
            sum += perfect(i, j);

        }
        if (sum == i) {
            printf("%d\n", i);
        }
    }
    system("pause");
    return 0;
}

int perfect(int k, int x) //la funzione calcola i fattori dei numeri i progressivi
{
    int f = k % x;
    if (f == 0) {
        return x;
    } else {
        return 0;
    }
}

Ho un po' riordinato il codice, il problema comunque era che il secondo for non doveva essere con j<=i ma solo j<i perchè il numero stesso non si conta. Poi ho spostato la stampa fuori dal for così stampa i risultati una volta sola.
Ti consiglio di scrivere il codice in un modo più leggibile (usa le parentesi graffe negli if), ci metti più righe ma ti semplifica molto quando devi trovare degli errori

 

[Emi02]

Perfetto vi ringrazio entrambi, proverò anche a rifarlo nel modo di @BAT

 

[BAT]

Cosi dovrebbe funzionare

se funziona non lo so perché non l'ho testata, ma è comunque programmata male: se tu chiami una funzione perfect, mi aspetto che essa dia true/false se il numero in input (uno solo, non 2 parametri); la tua funzione invece ritorna true se un certo numero x è divisore di k, il che è inutile dato che la cosa si fa con l'operazione di modulo %

@Eren88

 

[Emi02]

se funziona non lo so perché non l'ho testata, ma è comunque programmata molto male: se tu chiami una funzione perfect, mi aspetto che essa dia true/false se il numero in input (uno solo, non 2 paramentri); la tua funzione invece ritorna true se un certo numero x è divisore di k, il che è inutile

@Eren88

In realtà l'esercizio mi chiede di cercarlo alla cieca, quindi il mio era un tentativo di forza bruta però mi rendo conto che è molto carente.

 

[Eren88]

In effetti avrebbe più senso così:

#include <stdio.h>
#include <stdlib.h>

int main()
{
    printf("Di seguito verranno stampati tutti i numeri perfetti da 1 a 1000\n");
    for (int i = 1; i <= 1000; i++) { //tramite un for andiamo a testare tutti i numeri fino a 1000
        int sum = 0;
        for (int j = 1; j < i; j++) { //j individua il divisore
            if (i % j == 0) {
                sum = sum + j;
            }
        }
        if (sum == i) {
            printf("%d\n", i);
        }
    }
    system("pause");
    return 0;
}

La funzione non serviva a niente

 

[BAT]

In realtà l'esercizio mi chiede di cercarlo alla cieca, quindi il mio era un tentativo di forza bruta però mi rendo conto che è molto carente.

beh la forza bruta devi usarla nel senso che vanno trovati tutti i divisori (e poi sommati)

In effetti avrebbe più senso così:

esattamente, basta che piazzi il ciclo che fa il controllo in un funzione esterna perfect, e l'esercizio è risolto

 

[DispatchCode]

In effetti avrebbe più senso così:

#include <stdio.h>
#include <stdlib.h>

int main()
{
    printf("Di seguito verranno stampati tutti i numeri perfetti da 1 a 1000\n");
    for (int i = 1; i <= 1000; i++) { //tramite un for andiamo a testare tutti i numeri fino a 1000
        int sum = 0;
        for (int j = 1; j < i; j++) { //j individua il divisore
            if (i % j == 0) {
                sum = sum + j;
            }
        }
        if (sum == i) {
            printf("%d\n", i);
        }
    }
    system("pause");
    return 0;
}

La funzione non serviva a niente

Io toglierei quel system("pause"); in favore di un getchar(), che è portabile.

Per il calcolo comunque lo renderei più interessante usando un array come tabella per le somme parziali. Con un limite maggiore di 1000 si notano anche differenze nel tempo di esecuzione:

#include <stdio.h>

#define N 10000

void divisor_sums(int *sums, int n) 
{
    for (int i = 1; i <= N / 2; ++i) 
    {
        for (int j = i << 1; j <= n; j += i) {
            sums[j] += i;
        }
    }
}

int main() 
{
    int sums[N + 1] = {0};
    
    divisor_sums(sums, N);

    printf("Numeri perfetti fino a 1000:\n");
    
    for (int i = 2; i <= N; i++) 
    {            
        if (sums[i] == i) 
        {
            printf("%d\n", i);
        }
    }
    return 0;
}

Si evitano anche le divisioni.

 

[M1n021]

Per il singolo numero invece farei qualcosa del genere:

int is_perfect(unsigned int n)
{
    unsigned int sum = 1;
    for(unsigned int m = 2; m <= n / m; ++m)
    {
        if(!(n % m))
        {
            sum += m + n / m;
        }
    }
    return sum == n;
}

 

[BAT]

Per il singolo numero invece farei qualcosa del genere:

si può aggiungere all'inizio un controllo su pari/dispari ed evitare di fare operazioni sui dispari: al momento non sono noti numeri perfetti dispari, se esistono, è stato dimostrato che devono essere superiori a 10^2000, non rappresentabile da alcun tipo primitivo attuale di qualunque linguaggio di programmazione