Scomposizione in numeri primi

di il
11 risposte

Scomposizione in numeri primi

Programmo in C++ da poco e ci sto un po' prendendo confidenza facendo programmini semplici. stavo facendo un programma che scompone in fattori primi un numero dato ma tutti i numeri che contengono il 2 mi danno problemi infatti la potenze di due vengono saltate. mi spiego meglio: se ad esempio gli faccio scomporre 8 mi da 2 (omettendo gli altri due 2) ma anche con 24 mi stampa solamente 2 3. allego il codice.
#include<iostream>
#include<math.h>
using namespace std;
bool numeriprimi(long long numero)     //funzione che controlla se un numero è primo in modo da scomporre in fattori primi e non dire tutti i divisori
{
long long controllore;
for(controllore=2;controllore*controllore<=numero||numero==1;controllore++)
{
   if(numero%controllore==0||numero==1)
      {
        return false;
      }
}
if (controllore*controllore>numero&&numero!=1)
{
return true;
}
}
main()
{
long long x, indice=1;
cout<<"inserire il numero da scomporre:"<<endl;
cin>>x;
cout<<endl;
bool tf; //il bool mi serve sempre per controllare se il numero è primo (primo=1 non primo=0)
for (;indice<x+1;indice++)
{
    tf=numeriprimi(indice);
    if(x%indice==0&&tf==true)
    {
        cout<<indice<<endl;
        x/=indice;   //lo faccio ricominciare in modo che non si fermi al primo divisore che trova
        indice=2; 
    }
}
ringrazio in anticipo chi mi risponderà.

11 Risposte

  • Re: Scomposizione in numeri primi

    
    for (;indice<x+1;indice++)
    
    quell'indice++ ti frega, perché tu nell'if metti indice=2, ma poi ti viene incrementato. E poi non serve ricominciare con l'indice da 2 o da 1, basta non incrementarlo se indice è fattore primo. Inoltre, controllare se un numero è primo è subottimo, nel senso che il tempo che risparmi saltando alcune iterazioni è minore del tempo che ti serve per sapere se il numero è primo.
    Io farei
    
    int indice = 1;
    while(x > 1) {
        if(x % indice == 0) {
            cout << indice << endl;
            x /= indice;
        }
        else
            indice++;
    }
    
    così se 2 è divisore più volte verrà rilevato in iterazioni consecutive.
  • Re: Scomposizione in numeri primi

    Franzo ha scritto:


    Io farei
    ...
    così se 2 è divisore più volte verrà rilevato in iterazioni consecutive.
    - indice dovrebbe partire da 2, altrimenti si genera un loop infinito;
    - sostituirei l'if/else con un secondo ciclo while;
    - invece di incrementare indice di 1, considererei solo i numeri dispari;
    - cosa più importante, in riferimento al ciclo while più esterno, invece di continuare finchè n!=1, mi fermerei quando ho la certezza che il valore attuale di x è un numero primo. Per esempio per x=163 basta analizzare i divisori fino a 13 per affermare che si tratta di un numero primo.
  • Re: Scomposizione in numeri primi

    Franzo ha scritto:


    
    for (;indice<x+1;indice++)
    
    quell'indice++ ti frega, perché tu nell'if metti indice=2, ma poi ti viene incrementato. E poi non serve ricominciare con l'indice da 2 o da 1, basta non incrementarlo se indice è fattore primo. Inoltre, controllare se un numero è primo è subottimo, nel senso che il tempo che risparmi saltando alcune iterazioni è minore del tempo che ti serve per sapere se il numero è primo.
    Io farei
    
    int indice = 1;
    while(x > 1) {
        if(x % indice == 0) {
            cout << indice << endl;
            x /= indice;
        }
        else
            indice++;
    }
    
    così se 2 è divisore più volte verrà rilevato in iterazioni consecutive.
    Ma in questo modo non stamperà oltre ai fattori primi ripetuti tutti i divisori interi di x? (A parte il ciclo infinito con indice che parte da 1). Ma comunque non ho capito come mai mi stampa il due una sola volta.
  • Re: Scomposizione in numeri primi

    Nippolo ha scritto:


    Franzo ha scritto:


    Io farei
    ...
    così se 2 è divisore più volte verrà rilevato in iterazioni consecutive.
    - indice dovrebbe partire da 2, altrimenti si genera un loop infinito;
    - sostituirei l'if/else con un secondo ciclo while;
    - invece di incrementare indice di 1, considererei solo i numeri dispari;
    - cosa più importante, in riferimento al ciclo while più esterno, invece di continuare finchè n!=1, mi fermerei quando ho la certezza che il valore attuale di x è un numero primo. Per esempio per x=163 basta analizzare i divisori fino a 13 per affermare che si tratta di un numero primo.
    Ma se l'indice inizia da 2 poi come gli faccio fare la prima volta +1 e poi solo con i dispari?
  • Re: Scomposizione in numeri primi

    Scusatemi sono stato stupido, ovviamente stamperà solo i fattori primi dividendo x per l'indice come dite voi. Vi ringrazio delle indicazioni per migliorarlo, ma sinceramente non ho capito come mai saltava le potenze di 2 il mio vecchio programma. Ho capito che non ottimizzava i tempi ma nella mia testa doveva funzionare comunque in linea di principio.
  • Re: Scomposizione in numeri primi

    Le variabili devono avere dei nomi coerenti, non sarebbe meglio sostituire "indice" con "divisore"?
    Ma se l'indice inizia da 2 poi come gli faccio fare la prima volta +1 e poi solo con i dispari?
    i+=i%2+1
    ma sinceramente non ho capito come mai saltava le potenze di 2 il mio vecchio programma. Ho capito che non ottimizzava i tempi ma nella mia testa doveva funzionare comunque in linea di principio.
    Come già detto da Franzo, il problema sta nel modo in cui hai implementato il ciclo. Ipotizziamo che x sia divisibile per 2, essendo 2 un numero primo (tf=true) si entra nell'if, all'uscita dal quale sarà indice=2, a questo punto entra in gioco l'espressione di modifica del for (ossia indice++) che incrementa la variabile indice a 3. Ti renderai quindi conto che è possibile entrare una sola volta all'interno dell'if con la variabile indice pari a 2.
  • Re: Scomposizione in numeri primi

    Nippolo ha scritto:


    Le variabili devono avere dei nomi coerenti, non sarebbe meglio sostituire "indice" con "divisore"?
    Ma se l'indice inizia da 2 poi come gli faccio fare la prima volta +1 e poi solo con i dispari?
    i+=i%2+1
    ma sinceramente non ho capito come mai saltava le potenze di 2 il mio vecchio programma. Ho capito che non ottimizzava i tempi ma nella mia testa doveva funzionare comunque in linea di principio.
    Come già detto da Franzo, il problema sta nel modo in cui hai implementato il ciclo. Ipotizziamo che x sia divisibile per 2, essendo 2 un numero primo (tf=true) si entra nell'if, all'uscita dal quale sarà indice=2, a questo punto entra in gioco l'espressione di modifica del for (ossia indice++) che incrementa la variabile indice a 3. Ti renderai quindi conto che è possibile entrare una sola volta all'interno dell'if con la variabile indice pari a 2.
    Adesso ho capito, grazie della spiegazione della pazienza.
  • Re: Scomposizione in numeri primi

    Nippolo ha scritto:


    i+=i%2+1
    Oppure per velocizzare, due cicli separati, uno per provare se è divisibile per due e uno per i dispari a partire da 3, così si evita la divisione (o l'and, a seconda che il compilatore ottimizzi o meno) ad ogni iterazione (effettivamente non un gran peso)

    P.S. scusate per la gaffe del ciclo infinito
  • Re: Scomposizione in numeri primi

    #include<iostream>
    using namespace std;
    main()
    {
    long long x, indice=2;
    cout<<"inserire il numero da scomporre:"<<endl;
    cin>>x;
    cout<<endl;
    while(x>1)
    {
        while(x%indice==0)
        {
            cout<<indice<<endl;
            x/=indice;
        }
        if(indice%2==0)
        {
            indice++;
        }
        if(indice%2==1)
        {
            indice+=2;
        }
        if(indice*indice>x)
        {
            cout<<x<<endl;
            break;
        }
    }}
    quindi mi confermate che questo sarebbe il codice che ottimizza meglio il procedimento?
  • Re: Scomposizione in numeri primi

    prog2.0 ha scritto:


    quindi mi confermate che questo sarebbe il codice che ottimizza meglio il procedimento?
    Diciamo che senza la conoscenza del linguaggio assembly (e a volte non basta nemmeno quella) è difficile sapere quale forma è più veloce.
    Puoi fare ulteriori modifiche per sveltirlo, tipo la condizione di questo if
    if(indice*indice>x)
    può direttamente andare al posto di quella del while (negandola) e il cout fuori dal while; e al posto della coppia
    
        if(indice%2==0)
        {
            indice++;
        }
        if(indice%2==1)
        {
            indice+=2;
        }
    
    è più veloce

    Nippolo ha scritto:


    i+=i%2+1
    In ogni caso, se usi gcc da linea di comando, puoi usare -Ofast (O maiuscola) e il compilatore ottimizzerà il tuo codice per renderlo più veloce (a livello di compilazione, quindi ciò che tu vedi è solo un programma più veloce, non ti cambia il codice).

    P.S. assumo che tu per codice "ottimo" intenda codice più veloce possibile
  • Re: Scomposizione in numeri primi

    Inoltre al posto di
    while(i * i <= x)
    utilizzerei
    while(i <= x / i)
    per diminuire la probabilità di overflow.
Devi accedere o registrarti per scrivere nel forum
11 risposte