[Algoritmi] Semiprimi
Un esercizio ci dice di trovare un algoritmo che passato in input un intero n, ci dice se quest'ultimo è un semiprimo o meno. La complessità deve essere \( O(\surd n) \)
Io mi sono cimentato in questo esercizio creando queste due funzioni in Python:
Notiamo che nel for della funzione semiprimo, nel caso peggiore, potremmo avere la lista "divisori" riempita con esattamente \( \surd n \) elementi in ordine crescente.
Il mio ragionamento è stato questo:
\( o(\surd i1) \) + \( o(\surd i2) \) + \( o(\surd i3) \) + . . . + \( o(\surd n) \) = \( o(\surd n) \)
l'uguaglianza è giustificata poiché l'operazione più pesante sarà proprio l'ultima.
La soluzione però mi sembra troppo comoda . . . cosa sto sbagliando?
Io mi sono cimentato in questo esercizio creando queste due funzioni in Python:
Notiamo che nel for della funzione semiprimo, nel caso peggiore, potremmo avere la lista "divisori" riempita con esattamente \( \surd n \) elementi in ordine crescente.
Il mio ragionamento è stato questo:
\( o(\surd i1) \) + \( o(\surd i2) \) + \( o(\surd i3) \) + . . . + \( o(\surd n) \) = \( o(\surd n) \)
l'uguaglianza è giustificata poiché l'operazione più pesante sarà proprio l'ultima.
La soluzione però mi sembra troppo comoda . . . cosa sto sbagliando?
Risposte
La tua uguaglianza sarebbe valida solo se il numero di divisori fosse costante, ma in questo caso, come hai già osservato, è nell'ordine di \(\sqrt{N}\). La complessità nel tuo caso è probabilmente \(O(N)\).
Il numero di divisori di un semi-primo è comunque sempre uguale a \(4\). Se \(N = p\,q\) allora questi divisori sono \(1, p, q, N\). Siccome nel tuo caso non consideri il numero \(1\) e ti fermi a \(\sqrt{N}\), vuol dire che hai un solo valore restituito dalla tua funzione. In effetti puoi avere un solo valore solo in due casi:
1. \(N = p^k\) per \(k \in \{2, 3\}\). In questo caso i divisori sono rispettivamente \(1, p, p^2 = N\) (semi-primo) e \(1, p, p^2, p^3 = N\). In entrambi i casi la tua funzione restituisce solo \(p.\)
2. \(N = p\,q\) è semi-primo con primi distinti.
Se il numero di primi fosse maggiore di \(2\) allora il minimo numero di divisori sarebbe \(8\): \(1, p, q, r, p\,q, p\,r, q\,r, p\,q\,r = N\). La tua funzione ne restituirebbe quindi almeno \(3\).
Il numero di divisori di un semi-primo è comunque sempre uguale a \(4\). Se \(N = p\,q\) allora questi divisori sono \(1, p, q, N\). Siccome nel tuo caso non consideri il numero \(1\) e ti fermi a \(\sqrt{N}\), vuol dire che hai un solo valore restituito dalla tua funzione. In effetti puoi avere un solo valore solo in due casi:
1. \(N = p^k\) per \(k \in \{2, 3\}\). In questo caso i divisori sono rispettivamente \(1, p, p^2 = N\) (semi-primo) e \(1, p, p^2, p^3 = N\). In entrambi i casi la tua funzione restituisce solo \(p.\)
2. \(N = p\,q\) è semi-primo con primi distinti.
Se il numero di primi fosse maggiore di \(2\) allora il minimo numero di divisori sarebbe \(8\): \(1, p, q, r, p\,q, p\,r, q\,r, p\,q\,r = N\). La tua funzione ne restituirebbe quindi almeno \(3\).
Non mi sono ben chiare alcune parti della tua delucidazione.
C'è online una dimostrazione di ciò? O è sapere comune? Che materia avrei dovuto studiarlo per sapere una cosa del genere?
Il n°1 non è un numero primo, quindi non può andare a formare un semiprimo . . . o sbaglio? Almeno online quando si parla di numeri primi si parte sempre da 2.
Un solo valore? Intendi il true o il false?
O intendi i divisori primi del numero n?
Il resto non l'ho capito perché ti ho perso in quest'ultima frase sul valore.
"apatriarca":
Il numero di divisori di un semi-primo è comunque sempre uguale a \(4\). Se \(N = p\,q\) allora questi divisori sono \(1, p, q, N\).
C'è online una dimostrazione di ciò? O è sapere comune? Che materia avrei dovuto studiarlo per sapere una cosa del genere?
"apatriarca":
Siccome nel tuo caso non consideri il numero \(1\) e ti fermi a \(\sqrt{N}\)
Il n°1 non è un numero primo, quindi non può andare a formare un semiprimo . . . o sbaglio? Almeno online quando si parla di numeri primi si parte sempre da 2.
"apatriarca":
vuol dire che hai un solo valore restituito dalla tua funzione.
Un solo valore? Intendi il true o il false?
O intendi i divisori primi del numero n?
Il resto non l'ho capito perché ti ho perso in quest'ultima frase sul valore.
Un divisore \(d\) di un numero intero \(n\) è un numero intero per cui \( d\,m = n \) per un qualche altro numero intero \(m\). Quindi \(1\) e \(n\) sono sempre due divisori di \(n\) (gli unici nel caso di un numero primo). Se \(n = p_1^{\alpha_1} \cdots p_k^{\alpha_k}\) è la fattorizzazione con numeri primi del numero allora il numero di divisori sarà uguale a \( \prod_{i=1}^k (\alpha_i + 1) \). Per dimostrarlo è sufficiente osservare che la fattorizzazione in numeri primi di un divisore sarà formata solo da numeri primi presenti anche nella fattorizzazione di \(n\) e che le corrispondenti potenze saranno al più uguali a quelle di \(n\). Considereremo insomma tutti i numeri con fattorizzazione \( p_1^{\beta_1} \cdots p_k^{\beta_k}\) con \(0 \leq \beta_i \leq \alpha_i\) per ogni \(1 \leq i \leq k\). È facile vedere come il numero totale di fattorizzazioni di questo tipo sia dato dalla formula precedente.
Nel caso di numeri semiprimi abbiamo due tipi di fattorizzazioni: \(n = p^2\) o \(n = p\,q\). Nel primo caso abbiamo \(3\) divisori e nel secondo \(4\) e sono dati dalle formule che ti ho scritto in precedenza. La tua funzione restituirà tuttavia una lista con un solo divisore al suo interno in entrambi i casi.
Tuttavia c'è un altro caso da considerare con \(4\) divisori (e uno solo presente nella tua lista di divisori) ed è quello in cui la fattorizzazione sia della forma \(n = p^3\). Per verificare che un numero sia semiprimo è insomma sufficiente verificare che ci sia un solo valore nella lista dei divisori restituita da [tt]isPrime[/tt] ed escludere il caso in cui il tuo numero sia un cubo perfetto di un primo (devi solo verificare se il cubo del divisore sia uguale al numero).
Nel caso di numeri semiprimi abbiamo due tipi di fattorizzazioni: \(n = p^2\) o \(n = p\,q\). Nel primo caso abbiamo \(3\) divisori e nel secondo \(4\) e sono dati dalle formule che ti ho scritto in precedenza. La tua funzione restituirà tuttavia una lista con un solo divisore al suo interno in entrambi i casi.
Tuttavia c'è un altro caso da considerare con \(4\) divisori (e uno solo presente nella tua lista di divisori) ed è quello in cui la fattorizzazione sia della forma \(n = p^3\). Per verificare che un numero sia semiprimo è insomma sufficiente verificare che ci sia un solo valore nella lista dei divisori restituita da [tt]isPrime[/tt] ed escludere il caso in cui il tuo numero sia un cubo perfetto di un primo (devi solo verificare se il cubo del divisore sia uguale al numero).
Prima di cominciare con la citazione volevo solo ringraziarti per la tua pazienza e velocità nel rispondermi, per ora penso di aver capito la soluzione per testare se il numero è semiprimo o meno, cioè semplicemente aggiungere alla mia funzione il controllo che il numero di divisori sia pari a 1, giusto?
Non ho capito il senso di questa spiegazione, cosa dimostra? La correttezza della formula?
Non riesco a vedere la correlazione tra le due cose. Come spiegheresti allora il "+1" nella formula?
Abbiamo solo quei due casi perché i semiprimi per definizione saranno la moltiplicazione di DUE numeri primi e non di più, giusto? (Sto cominciando a capire
)
La mia funzione restituirà sempre un solo divisore perché:
1) L' \( 1 \) lo escludo in partenza;
2) I divisori contati arriveranno fino a radice di n, quindi trovato un divisore, non troverò l'altro;
3)L' \( n \)
Ma questo non sarà semiprimo visto che sarebbe la moltiplicazione di 3 numeri primi(anche se uguali tra loro), giusto . . . ?
Uhm, perché fermarsi al cubo? Perché non dover controllare che il divisore elevata alla quarta/quinta ecc . . . non sia uguale al mio risultato?
"apatriarca":
Per dimostrarlo è sufficiente osservare che la fattorizzazione in numeri primi di un divisore sarà formata solo da numeri primi presenti anche nella fattorizzazione di \(n\) e che le corrispondenti potenze saranno al più uguali a quelle di \(n\). Considereremo insomma tutti i numeri con fattorizzazione \( p_1^{\beta_1} \cdots p_k^{\beta_k}\) con \(0 \leq \beta_i \leq \alpha_i\) per ogni \(1 \leq i \leq k\). È facile vedere come il numero totale di fattorizzazioni di questo tipo sia dato dalla formula precedente.
Non ho capito il senso di questa spiegazione, cosa dimostra? La correttezza della formula?
Non riesco a vedere la correlazione tra le due cose. Come spiegheresti allora il "+1" nella formula?
"apatriarca":
Nel caso di numeri semiprimi abbiamo due tipi di fattorizzazioni: \(n = p^2\) o \(n = p\,q\). Nel primo caso abbiamo \(3\) divisori e nel secondo \(4\) e sono dati dalle formule che ti ho scritto in precedenza. La tua funzione restituirà tuttavia una lista con un solo divisore al suo interno in entrambi i casi.
Abbiamo solo quei due casi perché i semiprimi per definizione saranno la moltiplicazione di DUE numeri primi e non di più, giusto? (Sto cominciando a capire
)La mia funzione restituirà sempre un solo divisore perché:
1) L' \( 1 \) lo escludo in partenza;
2) I divisori contati arriveranno fino a radice di n, quindi trovato un divisore, non troverò l'altro;
3)L' \( n \)
"apatriarca":
Tuttavia c'è un altro caso da considerare con \(4\) divisori (e uno solo presente nella tua lista di divisori) ed è quello in cui la fattorizzazione sia della forma \(n = p^3\).
Ma questo non sarà semiprimo visto che sarebbe la moltiplicazione di 3 numeri primi(anche se uguali tra loro), giusto . . . ?
"apatriarca":
Per verificare che un numero sia semiprimo è insomma sufficiente verificare che ci sia un solo valore nella lista dei divisori restituita da [tt]isPrime[/tt] ed escludere il caso in cui il tuo numero sia un cubo perfetto di un primo (devi solo verificare se il cubo del divisore sia uguale al numero).
Uhm, perché fermarsi al cubo? Perché non dover controllare che il divisore elevata alla quarta/quinta ecc . . . non sia uguale al mio risultato?
1. Ogni \( \beta_i\) può assumere uno tra \( \alpha_i + 1 \) valori da \(0\) a \(\alpha_i\). Quindi il numero totale di combinazioni è \( \prod_{i=0}^k (\alpha_i + 1)\). Se usiamo questa formula nel caso dei semi-primi otteniamo \(3\) o \(4\) divisori a seconda che i due primi siano uguali o diversi.
2. Il numero di valori restituiti dalla tua funzione sarà uguale a circa metà dei divisori contati sopra. Più in dettaglio, se \(2\,k + l\) sono i divisori contati con la formula sopra, la tua funzione ne restituirà \(k + l - 1\). Quindi se i divisori sono \(2\) (numero primo) non avrai alcun divisore nella tua lista, se sono \(3\) o \(4\) avrai un solo valore nella lista, se sono \(5\) o \(6\) ne avrai \(2\) e così via. I semiprimi hanno \(3\) o \(4\) divisori per cui la tua funzione avrà un solo valore restituito dalla lista.
3. Se un numero è il cubo di un primo allora avrà \(4\) divisori come un semiprimo e un solo valore nella lista restituita dalla tua funzione. È quindi necessario escludere questo caso esplicitamente. Se la potenza è maggiore il numero di divisori sarà almeno uguale a \(5\) e quindi avrai almeno \(2\) valori nella tua lista. Discorso simile con almeno 3 primi, in cui il numero di divisori è necessariamente maggiore a quello di un semiprimo.
2. Il numero di valori restituiti dalla tua funzione sarà uguale a circa metà dei divisori contati sopra. Più in dettaglio, se \(2\,k + l\) sono i divisori contati con la formula sopra, la tua funzione ne restituirà \(k + l - 1\). Quindi se i divisori sono \(2\) (numero primo) non avrai alcun divisore nella tua lista, se sono \(3\) o \(4\) avrai un solo valore nella lista, se sono \(5\) o \(6\) ne avrai \(2\) e così via. I semiprimi hanno \(3\) o \(4\) divisori per cui la tua funzione avrà un solo valore restituito dalla lista.
3. Se un numero è il cubo di un primo allora avrà \(4\) divisori come un semiprimo e un solo valore nella lista restituita dalla tua funzione. È quindi necessario escludere questo caso esplicitamente. Se la potenza è maggiore il numero di divisori sarà almeno uguale a \(5\) e quindi avrai almeno \(2\) valori nella tua lista. Discorso simile con almeno 3 primi, in cui il numero di divisori è necessariamente maggiore a quello di un semiprimo.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo