Scomposizione in numeri primi

prog2.0

il 07 set 2018, 18:09

11 risposte

prog2.0

Pochi posts

Iscritto da: ago, 2018

Messaggi:: 8

Scomposizione in numeri primi

07 set 2018, 18:13

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

F
Franzo
Pochi posts
Iscritto da
ago, 2018
Messaggi:
26
Re: Scomposizione in numeri primi
07 set 2018, 18:29
```
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.
Nippolo
Molto attivo
Iscritto da
mar, 2018
Messaggi:
1239
Re: Scomposizione in numeri primi
07 set 2018, 19:42
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.
P
prog2.0
Pochi posts
Iscritto da
ago, 2018
Messaggi:
8
Re: Scomposizione in numeri primi
08 set 2018, 01:22
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.
P
prog2.0
Pochi posts
Iscritto da
ago, 2018
Messaggi:
8
Re: Scomposizione in numeri primi
08 set 2018, 01:30
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?
P
prog2.0
Pochi posts
Iscritto da
ago, 2018
Messaggi:
8
Re: Scomposizione in numeri primi
08 set 2018, 01:34
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.
Nippolo
Molto attivo
Iscritto da
mar, 2018
Messaggi:
1239
Re: Scomposizione in numeri primi
08 set 2018, 12:18
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.
P
prog2.0
Pochi posts
Iscritto da
ago, 2018
Messaggi:
8
Re: Scomposizione in numeri primi
08 set 2018, 13:16
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.
F
Franzo
Pochi posts
Iscritto da
ago, 2018
Messaggi:
26
Re: Scomposizione in numeri primi
08 set 2018, 13:24
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

prog2.0

Pochi posts

Iscritto da: ago, 2018

Messaggi:: 8

Re: Scomposizione in numeri primi

08 set 2018, 16:05

#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?

F
Franzo
Pochi posts
Iscritto da
ago, 2018
Messaggi:
26
Re: Scomposizione in numeri primi
08 set 2018, 17:36
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
Nippolo
Molto attivo
Iscritto da
mar, 2018
Messaggi:
1239
Re: Scomposizione in numeri primi
08 set 2018, 18:02
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