Scomposizione fattori primi

di
pinothegamer
il
12 risposte
P
pinothegamer
Pochi posts
Iscritto da
apr, 2018
Messaggi:
6

Scomposizione fattori primi

Buonasera a tutti, sono qui perchè non riesco a capire il programma non stampi nulla alla fine dell'ordinamento... ecco qui metto il codice.

#include <iostream>
using namespace std;
#define max 2000
 
int main(){
    int data[max], n[2], key, b=2, div=0;
    cout<<"SCOMPOSITORE FATTORI PRIMI"<<endl;
    do{                    
           cout<<"\n\n\nInserire il numero di cui si desidera conoscere la fattorizzazione; se si vuole interrompere il programma inserire 0: ";
           cin>>n[0];
           if(n[0]==0){
                   system("PAUSE");
                   return 0;
                   }
           while(n[0]<=1){
                       cout<<"\nERRORE: INSERIRE UN NUMERO NATURALE DIVERSO DA 1 E 0!"<<endl;
                       cin>>n[0];
                       }
           n[1]=n[0];
           for(int a=0; data[a]=!1; a++){
                   while(n[0]%b!=0){
                                    b++;
                                    }
                   n[0]/=b;
                   data[a]=b;
                   b=2;
                   }
           while(data[div]!=0){
                               div++;
                               }
           for(int c=1; c<div; c++){
                   key=data[c];
                   for(int d=c-1; d>=0 && data[d]>key; d--){
                           data[d+1]=data[d];
                           data[d]=key;
                           }
                   }
           cout<<"\nI fattori che compongono il numero "<<n[1]<<" sono: ";
           for(int e=0; e<div; e++){
                   cout<<data[e]<<"*";
                   }
           }while(n[0]!=0);
    system("PAUSE");
    return 0;
}
Sono nuovo su questo forum e spero di aver rispettato tutte le regole. Grazie in anticipo

12 Risposte

  • Nippolo
    Nippolo
    Molto attivo
    Iscritto da
    mar, 2018
    Messaggi:
    1237

    Re: Scomposizione fattori primi

    Ho iniziato a leggere il codice, ma mi sono fermato al primo ciclo for.
    data[a]=!1 cosa significa?
    Intendevi forse data[a] != 1? In questo caso non avrebbe molto senso dal momento che non avendo inizializzato l'array data questo conterrà valori casuali.
    Se invece hai scritto volutamente così, c'è cmq qualcosa che non va, in quanto la condizione del ciclo è data dalla variabile data dopo avergli assegnato il valore !1 (ossia 0 e quindi falso). In pratica il programma non entra proprio all'interno di quel ciclo for.


    EDIT:
    Sarebbe utile se ci spiegassi meglio qual è la tua idea. Cosa ti aspetti che faccia l'algoritmo che hai implementato?
  • P
    pinothegamer
    Pochi posts
    Iscritto da
    apr, 2018
    Messaggi:
    6

    Re: Scomposizione fattori primi

    Nippolo ha scritto:

    Ho iniziato a leggere il codice, ma mi sono fermato al primo ciclo for.
    data[a]=!1 cosa significa?
    Intendevi forse data[a] != 1? In questo caso non avrebbe molto senso dal momento che non avendo inizializzato l'array data questo conterrà valori casuali.
    Se invece hai scritto volutamente così, c'è cmq qualcosa che non va, in quanto la condizione del ciclo è data dalla variabile data dopo avergli assegnato il valore !1 (ossia 0 e quindi falso). In pratica il programma non entra proprio all'interno di quel ciclo for.


    EDIT:
    Sarebbe utile se ci spiegassi meglio qual è la tua idea. Cosa ti aspetti che faccia l'algoritmo che hai implementato?



    Innanzitutto mi aspettavo che il programma alla fine di tutto stampasse direttamente tutti i fattori che compongono il numero che viene inserito, quindi ho pensato di utilizzare l'array data[a] come ogni divisore: l'espressione data[a]!=0 l'ho usata appunto perché l'ultimo divisore sarà sempre 1, quindi ho pensato che se non venisse inserita questa verifica il ciclo continuerebbe finché non si arriva fino all'ultimo elemento dell'array e quando arriverà il momento della stampa verranno stampati una marea di numeri inutili.
    Spero di essere stato abbastanza chiaro.
  • Nippolo
    Nippolo
    Molto attivo
    Iscritto da
    mar, 2018
    Messaggi:
    1237

    Re: Scomposizione fattori primi

    Se ci pensi però nel tuo programma è impossibile che un elemento dell'array data sia uguale a 1, infatti esso andrà a memorizzare i vari divisori di n[1] che saranno >=2 visto che inizializzi la variabile b a 2 e poi la incrementi.
    L'idea cmq è quasi giusta, nel senso che in quella condizione deve essere un'altra variabile ad essere diversa da 1. Pensaci su.

    Per il momento cominciamo col rendere il programma funzionante, poi dopo c'è da ottimizzare un bel po' di cose nel codice.


    P.s.
    Qual è lo scopo di quel doppio ciclo for dove utilizzi la variabile key?
  • P
    pinothegamer
    Pochi posts
    Iscritto da
    apr, 2018
    Messaggi:
    6

    Re: Scomposizione fattori primi

    Nippolo ha scritto:

    L'idea cmq è quasi giusta, nel senso che in quella condizione deve essere un'altra variabile ad essere diversa da 1. Pensaci su.
    Ora ho capito qual era il problema e al posto di data[a]!=1 ho messo n[0]!=1.

    P.s.
    Qual è lo scopo di quel doppio ciclo for dove utilizzi la variabile key?
    Il ciclo for nel quale utilizzo la variabile key mi serve per riordinare gli elementi in ordine crescente in questo caso, e lo uso per non avere gli stessi numeri in posizioni diverse. Avrei preferito che il programma stampasse le potenze di un numero nel caso si ripetesse più volte ma per il momento mi va bene così.
  • Nippolo
    Nippolo
    Molto attivo
    Iscritto da
    mar, 2018
    Messaggi:
    1237

    Re: Scomposizione fattori primi

    Il ciclo for nel quale utilizzo la variabile key mi serve per riordinare gli elementi in ordine crescente in questo caso, e lo uso per non avere gli stessi numeri in posizioni diverse.
    Premesso che non mi sono soffermato a capire cosa avviene realmente in quel doppio ciclo for, se il suo scopo è quello di ordinare l'array, allora è inutile in quanto il vettore data, per le modalità con cui viene riempito, risulta già ordinato.
    Ora ho capito qual era il problema e al posto di data[a]!=1 ho messo n[0]!=1.
    Ora il programma funziona, ma ci sono varie cose da ottimizzare:
    - il suddetto doppio ciclo for come già detto risulta superfluo;
    - affinché i divisori di un eventuale inserimento dopo il primo siano visualizzati correttamente, devi inizializzare la variabile div nuovamente a 0;
    - il ciclo while in cui incrementi la variabile div può essere evitato se incrementi div nel ciclo for precedente. O meglio ancora puoi utilizzare per il ciclo for la variabile div al posto della variabile a;
    - evita di utilizzare il system("PAUSE");
    - il return 0 finale è superfluo e sostituirei il primo con un semplice break;
    - se inserisci come primo numero 1 poi non hai la possibilità di uscire dal programma, aggiusterei quindi la parte relativa all'inserimento;
    - l'unico motivo per cui utilizzi l'array n è che n[0] viene modificato e alla fine devi stampare n[1], ma se stampi il numero inserito dall'utente prima del ciclo for principale, basterebbe una semplice variabile al posto di un array di due elementi;
    - un discorso simile può essere fatto per l'array data se stampi i divisori man mano che vengono trovati. In tal caso anche la variabile div non servirà più e il ciclo for principale può essere sostituito da un ciclo while.

    Resta poi da ottimizzare la parte prettamente logica. Dopo posto quali sono i punti su cui intervenire.
  • P
    pinothegamer
    Pochi posts
    Iscritto da
    apr, 2018
    Messaggi:
    6

    Re: Scomposizione fattori primi

    Nippolo ha scritto:

    Ora il programma funziona, ma ci sono varie cose da ottimizzare:
    - il suddetto doppio ciclo for come già detto risulta superfluo;
    - affinché i divisori di un eventuale inserimento dopo il primo siano visualizzati correttamente, devi inizializzare la variabile div nuovamente a 0;
    - il ciclo while in cui incrementi la variabile div può essere evitato se incrementi div nel ciclo for precedente. O meglio ancora puoi utilizzare per il ciclo for la variabile div al posto della variabile a;
    - evita di utilizzare il system("PAUSE");
    - il return 0 finale è superfluo e sostituirei il primo con un semplice break;
    - se inserisci come primo numero 1 poi non hai la possibilità di uscire dal programma, aggiusterei quindi la parte relativa all'inserimento;
    - l'unico motivo per cui utilizzi l'array n è che n[0] viene modificato e alla fine devi stampare n[1], ma se stampi il numero inserito dall'utente prima del ciclo for principale, basterebbe una semplice variabile al posto di un array di due elementi;
    - un discorso simile può essere fatto per l'array data se stampi i divisori man mano che vengono trovati. In tal caso anche la variabile div non servirà più e il ciclo for principale può essere sostituito da un ciclo while.

    Resta poi da ottimizzare la parte prettamente logica. Dopo posto quali sono i punti su cui intervenire.
    Sono riuscito a ottimizzare il programma seguendo i tuoi consigli e questo è il risultato 
    #include <iostream>
using namespace std;
 
int main(){
    long long int n, b=1;
    cout<<"SCOMPOSITORE FATTORI PRIMI"<<endl;
    do{                  
           cout<<"\n\n\n°Inserire il numero di cui si desidera conoscere la fattorizzazione; se si vuole interrompere il programma inserire 0 oppure 1: ";
           cin>>n;
           if(n==0 || n==1){
                   cout<<"\n\n"<<endl;
                   break;
                   }
           while(n<=1){
                       cout<<"\n°ERRORE: INSERIRE UN NUMERO NATURALE DIVERSO DA 1 E 0!"<<endl;
                       cin>>n;
                       }
           
           cout<<"\nI fattori che compongono il numero "<<n<<" sono: ";
           for(int a=0; n!=1; a++){
                   while(n%b!=0){
                                    b++;
                                    }
                   n/=b;
                   cout<<b<<"; ";
                   b=2;
                   }
           }while(n!=0 || n!=1);
}
    Ti ringrazio di cuore per avermi fatto notare molte cose superflue: mi sei stato di grande aiuto
    Nel caso in cui ci siano altre cose da migliorare sono ben accetto nel ricevere consigli
  • Nippolo
    Nippolo
    Molto attivo
    Iscritto da
    mar, 2018
    Messaggi:
    1237

    Re: Scomposizione fattori primi

    Mi fa piacere esserti stato d'aiuto.

    Il codice adesso va molto meglio. Qualche osservazione:
    - considera il ciclo do/while più esterno, la condizione (n != 0 || n != 1) sarà sempre vera anche se n è uguale a 0 o a 1. Forse volevi usare &&? In questo caso però la condizione sarà sempre falsa in quanto a quel punto del codice n è sempre uguale a 1. Io farei in questo modo per controllare l'inserimento: al posto del do/while userei un while con condizione sempre vera, quindi se n è uguale a 0 esci dal ciclo con break, mentre se n è uguale a 1 o è un numero negativo ricominci il ciclo con l'istruzione continue;
    - il ciclo for è inutile, visto che non utilizzi la variabile a basta un semplice while;
    - non ha molto senso inizializzare la variabile b a 1 visto che qualsiasi numero è divisibile per 1. ovviamente b va inizializzata a 2 e se scegli bene la riga in cui inserire questa istruzione sarà sufficiente un'unica inizializzazione.

    Per quanto riguarda la parte logica la tua idea è quella di trovare tutti i divisori finché n non sarà uguale a 1 (anche se io ragionerei in modo diverso). In ogni caso il tuo algoritmo può essere migliorato evitando di far partire ogni volta b da 2. Mi spiego meglio, ipotizziamo che n=539, b andrà da 2 a 7 (a questo punto n=77), poi andrà di nuovo da 2 a 7 (a questo punto n=11) e poi andrà da 2 a 11 (a questo punto n=1). Ciò può essere evitato se una volta trovato un divisore controlli se n è divisibile più volte per b. In questo modo infatti non serve più far ripartire b da 2, ma basta incrementarlo. Tornando all'esempio precedente (n=539), b andrà da 2 a 7 (a questo punto n=77 e poi n=11) e poi andrà da 7 a 11(a questo punto n=1).
    Un modo per velocizzare ulteriormente il programma sarebbe quello di considerare oltre al 2 solo valori di b dispari, in quanto tutti i numeri primi ovviamente non sono divisibili per 2 (quindi b=2,3,5,7,9...).
    Per quanto riguarda la mia idea la scrivo domani con calma.
  • Nippolo
    Nippolo
    Molto attivo
    Iscritto da
    mar, 2018
    Messaggi:
    1237

    Re: Scomposizione fattori primi

    L'idea su cui si basa il tuo algoritmo consiste nel trovare tutti i possibili divisori di n finché n non è uguale a 1.
    Io invece ragionerei in modo diverso e, nella ricerca dei divisori, mi fermerei quando ho la certezza che n sia un numero primo. Mi spiego meglio...
    Un numero non primo può essere scritto come prodotto di due o più numeri primi. Ipotizziamo n=31, nel tuo codice b varierà da 2 a 31, seguendo il mio ragionamento invece (e considerando come detto nel post precedente b=2,3,5,7,9,11...) b varierà solo da 2 a 7, infatti, una volta assodato che 31 non è divisibile per 5, la più piccola coppia di probabili divisori di n sarà composta da due 7, ma essendo 7*7=49 > 31 deduciamo che 31 non può avere divisori (esclusa la coppia costituita da 1 e se stesso), ovvero è un numero primo.
    Quindi la condizione che determina la fine del ciclo, che nel tuo caso è n!=1, diventerebbe n>=b*b o ancora meglio se si vuole evitare l'overflow n/b>=b (ottenuta dalla precedente dividendo a destra e sinistra per b).

    Spero di essere stato chiaro.
  • P
    pinothegamer
    Pochi posts
    Iscritto da
    apr, 2018
    Messaggi:
    6

    Re: Scomposizione fattori primi

    Dopo aver provato il tuo ragionamento mi si sono spalancati gli occhi
    Incredibile come possa aver complicato il programma all'inizio e di come tu sia riuscito a farlo diventare cortissimo

    Nippolo ha scritto:

    Mi fa piacere esserti stato d'aiuto.

    Il codice adesso va molto meglio. Qualche osservazione:
    - considera il ciclo do/while più esterno, la condizione (n != 0 || n != 1) sarà sempre vera anche se n è uguale a 0 o a 1. Forse volevi usare &&? In questo caso però la condizione sarà sempre falsa in quanto a quel punto del codice n è sempre uguale a 1. Io farei in questo modo per controllare l'inserimento: al posto del do/while userei un while con condizione sempre vera, quindi se n è uguale a 0 esci dal ciclo con break, mentre se n è uguale a 1 o è un numero negativo ricominci il ciclo con l'istruzione continue;
    Questa è l'unica cosa che non ho capito
    qui ti passo il codice aggiornato:
    #include <iostream>
using namespace std;
 
int main(){
    long long int n;
    cout<<"SCOMPOSITORE FATTORI PRIMI"<<endl;
    do{
           long long int b=2;                  
           cout<<"\n\n\nInserire il numero di cui si desidera conoscere la fattorizzazione; se si vuole interrompere il programma inserire 0 oppure 1: ";
           cin>>n;
           if(n==0 || n==1){
                   cout<<"\n\n"<<endl;
                   break;
                   }
           while(n<=1){
                       cout<<"\nERRORE: INSERIRE UN NUMERO NATURALE DIVERSO DA 1 E 0!"<<endl;
                       cin>>n;
                       }
           
           cout<<"\n°I fattori che compongono il numero "<<n<<" sono: ";
           while(n/b>=b){
                         if(n%b==0) {
                                    cout<<b<<"*";
                                    n/=b;
                                    }
                         else b++;
                         }
           cout<<n<<endl;
           }while(n!=0 || n!=1);
}
    Cosa dovrei fare con il while finale????
  • Nippolo
    Nippolo
    Molto attivo
    Iscritto da
    mar, 2018
    Messaggi:
    1237

    Re: Scomposizione fattori primi

    Dopo aver provato il tuo ragionamento mi si sono spalancati gli occhi
    Credevo non si capisse nulla da come l'ho spiegato.

    Per quanto riguarda il codice:
    - la variabile b la dichiarerei al di fuori del do/while (la posizione per l'inizializzazione è corretta) in modo che non venga distrutta e creata da capo ad ogni inserimento;
    - affinché venga controllato se n è divisibile più volte per b, sostituirei if(n % b == 0) con while(n % b == 0). L'else a quel punto non serve più;
    - come già detto sopra puoi escludere tutti i numeri pari maggiori di 2 dall'elenco dei probabili divisori in quanto non sono numeri primi. Per ottenere una sequenza del genere b=2,3,5,7,9... potresti usare la seguente formula b+=b%2+1;
    - per quanto riguarda il ciclo più esterno farei qualcosa del genere: 
    while(true)
    {
        cout << endl << "INSERIRE INTERO POSITIVO MAGGIORE DI 1 (0 PER USCIRE): ";
        cin >> n;
        if(n == 1 || n < 0)
        {
            cout << "INSERIMENTO NON VALIDO!";
            continue;
        }
        if(n == 0)
        {
            break;
        }
        b = 2;
        ...
        ...
    }
  • P
    pinothegamer
    Pochi posts
    Iscritto da
    apr, 2018
    Messaggi:
    6

    Re: Scomposizione fattori primi

    Ho sistemato tutto tranne alcune cose che non mi tornano, qui ti passo il codice... 
    #include <iostream>
using namespace std;
#define a 1
 
int main(){
    long long int n;
    cout<<"SCOMPOSITORE FATTORI PRIMI\n"<<endl;
    while(a==1){
           long long int b=2;                  
           cout<<"Inserire un numero naturale diverso da 1; inserire 0 per uscire: ";
           cin>>n;
           if(n==0){
                   cout<<"\n\n"<<endl;
                   break;
                   }
           if(n==1 || n<0){
                       cout<<"\nERRORE! ";
                       continue;
                       }
           
           cout<<"\n\n\n°I fattori che compongono il numero "<<n<<" sono: ";
           while(n/b>=b){
                         while(n%b==0) {
                                    cout<<b<<"*";
                                    n/=b;
                                    }
                         b+=b%2+1;
                         }
           cout<<n<<"\n\n\n"<<endl;
           }
}

    Nippolo ha scritto:

    - la variabile b la dichiarerei al di fuori del do/while (la posizione per l'inizializzazione è corretta) in modo che non venga distrutta e creata da capo ad ogni inserimento;
    La variabile l'ho messa dentro il ciclo perché se non la inizializzasse a 2 stamperebbe solo il numero inserito e non i suoi divisori;
    La cosa che non mi torna è la seguente: quando inserisco dei quadrati perfetti o dei multipli mi stampa sempre 1 alla fine; per esempio 72 è uguale a 2*2*2*3*3*1
    L'unico modo che mi è venuto in mente fare una cosa del genere alla fine dell'ultimo while: 
     if(n=!1){
                    cout<<n<<"\n\n\n"<<endl;
                    }
    Secondo te ci sono altri modi per risolvere il "problema"??
  • Nippolo
    Nippolo
    Molto attivo
    Iscritto da
    mar, 2018
    Messaggi:
    1237

    Re: Scomposizione fattori primi

    Ho letto il codice e va bene.

    Per quanto riguarda la condizione sempre vera che tu hai scritto come while(a==1), puoi anche scrivere direttamente while(1==1) o ancora meglio while(1) (o while(true) che è lo stesso).

    Per quanto riguarda la variabile b intendevo questo: 
    int main()
{
int b;
...
while(true)
{
b = 2;
...
    La cosa che non mi torna è la seguente: quando inserisco dei quadrati perfetti o dei multipli mi stampa sempre 1 alla fine...
    Secondo te ci sono altri modi per risolvere il "problema"??
    Quando il numero inserito non è primo ed è divisibile più volte per il suo massimo divisore (primo), allora per com'è impostato il codice sarà n=1 all'uscita del while.
    Per evitare che l'1 venga stampato va bene la tua soluzione.

    Se proprio vuoi mettere ancora mano al codice potresti mostrare la fattorizzazione con le potenze e avvisare nel caso in cui il numero inserito fosse primo.
Devi accedere o registrarti per scrivere nel forum
12 risposte