[C++] Algoritmo numeri primi
Salve a tutti.
Mi piacerebbe scrivere un algoritmo per individuare se un numero è primo oppure no.
Oppure una funzione che restituisca tutti i primi fino ad un input n dato.
Per entrambi i casi dopo aver fatto qualche ovvia scrematura (tipo che non sia pari o 5 mod10) conoscete qualche algoritmo differente dal costruire una booleiana ed iniziare a dividere il numero per tutti i numeri e vedere se il resto è 0 oppure no?
Una cosa del tipo
Grazie.
Mi piacerebbe scrivere un algoritmo per individuare se un numero è primo oppure no.
Oppure una funzione che restituisca tutti i primi fino ad un input n dato.
Per entrambi i casi dopo aver fatto qualche ovvia scrematura (tipo che non sia pari o 5 mod10) conoscete qualche algoritmo differente dal costruire una booleiana ed iniziare a dividere il numero per tutti i numeri e vedere se il resto è 0 oppure no?
Una cosa del tipo
bool IsPrime = true; int i=2; while(IsPrime && i<n/2) IsPrime = (n%i != 0) i++
Grazie.
Risposte
Il più famoso algoritmo è il Miller-Rabin, che è probabilistico (infatti formalmente è un algoritmo di "pseudo-primalità"). Non è difficile da implementare:
http://en.wikipedia.org/wiki/Miller%E2% ... nning_time
Puoi costruire una funzione booleana su questo.
http://en.wikipedia.org/wiki/Miller%E2% ... nning_time
Puoi costruire una funzione booleana su questo.
Grazie ora do una occhiata.
Sono partito dal suggerimento di apatriarca, questo è il risultato. Che ne pensate?
Ma non so. Avevo anche pensato di fare un vettore P=i per i=0,1,...,N e partire da qua.
EDIT: Il programma è sbagliato, restituisce numeri che non sono primi.
vector<int> P(1,2);
for(int i=1; i<=N;i++){ //Creo vettore col 2 e i successivi dispari;
P.push_back(2*i+1);
}
int i=1;
bool Iter=true; //Fisso un indice di partenza i ed una bool per
while(Iter){ //arrestare l'algoritmo (legato al quadrato vedere link wiki)
for(int j=(i+1); j<P.size(); j++){
if(P[j]%P[i] == 0) { P.erase (P.begin()+j); } // Qua il macello, se è multiplo
} // lo elimino (fatto col for)
Iter = P[i+1]*P[i+1]<=N; // Controllo se l'algo si deve farmere.
i++;
}
Ma non so. Avevo anche pensato di fare un vettore P=i per i=0,1,...,N e partire da qua.
EDIT: Il programma è sbagliato, restituisce numeri che non sono primi.
ciao DajeForte 
mi diresti che metodo hai utilizzato, è un qualche crivello?
non riesco a capirlo dal tuo codice.
mi diresti che metodo hai utilizzato, è un qualche crivello?
non riesco a capirlo dal tuo codice.
ciao hamming_burst 
Questa è a versione del codice aggiornata che dovrebbe essere corretta (almeno così pare).
Il crivello è quello di Eratostene linkato da apatriarca.
Si crea un vettore (P) dove P[0]=2 e poi tutti i dispari P[1]=3, P[2]=5 e così via
Da qua si iniziano ad eliminare gli elementi che non sono primi come descritto nel link di wiki.
Avendo già costruito gli elementi solo con i dispari, i pari sono già esclusi.
Si comincia allora dal numero 3 e si cercano nel vettore P i suoi multipli e li si eiminano.
Finiti questi si passa al numero "sopravvissuto" successivo a 3 che è il 5 e si cercano i suoi multipli e li si elminano.
Questo continua fino a che il numero di cui si andranno acercare i multipli è tale che il suo quadrato è superiore del numero massimo prensente nel vettore.
In particolare fisso un int i=1,
poi si verifica la condizione di arresto con il while (qua pernso si possa migliorare con P*P<=P[P.end()])
Dopo il while fisso il numero di cui devo cercare i multipli p=P
e vado a fare un for con j che varia da i+1 (non mi interessano i numeri <= a P) fino alla fine del vettore e chiedo:
se p=P divide p (if(P[j]%p == 0)) cancellalo (P.erase) altrimenti passa al j successivo (ovvero altrimenti non fa niente).
Finito con P=p incrementa i di 1; verifica la condizione (while) e se è vera vai a cercare i multipli di P[i+1].
Mi pare funzioni, prima non girava bene perchè creavo il vettore coi dispari fino a 2N+1 ma poi verifico la condizione di arresto come se i numeri fossero fino ad N (errore stupido).
vector<int> P(1,2);
for(int i=1; i<=N;i++){
P.push_back(2*i+1);
}
int i = 1;
while(P[i]*P[i]<=(2*N+1)){
int p = P[i];
for(int j=i+1; j<P.size(); j++){
if(P[j]%p == 0){
P.erase(P.begin()+j);
}
}
i++;
}
Questa è a versione del codice aggiornata che dovrebbe essere corretta (almeno così pare).
Il crivello è quello di Eratostene linkato da apatriarca.
Si crea un vettore (P) dove P[0]=2 e poi tutti i dispari P[1]=3, P[2]=5 e così via
Da qua si iniziano ad eliminare gli elementi che non sono primi come descritto nel link di wiki.
Avendo già costruito gli elementi solo con i dispari, i pari sono già esclusi.
Si comincia allora dal numero 3 e si cercano nel vettore P i suoi multipli e li si eiminano.
Finiti questi si passa al numero "sopravvissuto" successivo a 3 che è il 5 e si cercano i suoi multipli e li si elminano.
Questo continua fino a che il numero di cui si andranno acercare i multipli è tale che il suo quadrato è superiore del numero massimo prensente nel vettore.
In particolare fisso un int i=1,
poi si verifica la condizione di arresto con il while (qua pernso si possa migliorare con P*P<=P[P.end()])
Dopo il while fisso il numero di cui devo cercare i multipli p=P
e vado a fare un for con j che varia da i+1 (non mi interessano i numeri <= a P) fino alla fine del vettore e chiedo:
se p=P divide p (if(P[j]%p == 0)) cancellalo (P.erase) altrimenti passa al j successivo (ovvero altrimenti non fa niente).
Finito con P=p incrementa i di 1; verifica la condizione (while) e se è vera vai a cercare i multipli di P[i+1].
Mi pare funzioni, prima non girava bene perchè creavo il vettore coi dispari fino a 2N+1 ma poi verifico la condizione di arresto come se i numeri fossero fino ad N (errore stupido).
Non è così che si implementa il crivello di Eratostene. Il tuo codice ha in effetti una complessità molto più alta di quella del vero crivello di Eratostene. In particolare, nel tuo codice non ti limiti a considerare solo i multipli dei numeri primi, ma scorri tutti i numeri non ancora eliminati nei passaggi precedenti e l'eliminazione avviene in tempo lineare per ogni elemento eliminato. Il tuo codice è in effetti forse più lento del più semplice algoritmo di ricerca esaustiva.
Non ho tempo adesso di mettermi a descrivere a fondo come dovresti cambiare il codice per renderlo effettivamente il crivello di Eratostene, ma l'idea è quella di usare per esempio un vector che rappresenti se il numero è primo o meno (per cui nell'algoritmo semplicemente scorri l'array nelle posizioni corrispondenti ai multipli del numero e setti a false il valore).
Non ho tempo adesso di mettermi a descrivere a fondo come dovresti cambiare il codice per renderlo effettivamente il crivello di Eratostene, ma l'idea è quella di usare per esempio un vector
Avevo letto da due parti che si faceva così e questo è un esempio di implementazione fatto wiki
Adesso implementerò anche questa versione.
Grazie del feedback se poi vuoi spendere altre due parole io ti ascolto poi posterò anche l'altra.
Input: an integer n > 1
Let A be an array of Boolean values, indexed by integers 2 to n,
initially all set to true.
for i = 2, 3, 4, ..., while i ≤ n/2:
if A[i] is true:
for j = 2i, 3i, 4i, ..., while j ≤ n:
A[j] := false
Now all i such that A[i] is true are prime.
Adesso implementerò anche questa versione.
Grazie del feedback se poi vuoi spendere altre due parole io ti ascolto poi posterò anche l'altra.
Puoi partire da \(i^2\) per eliminare i multipli perché gli altri dovrebbero essere già stati eliminati nei cicli precedenti. Inoltre puoi fermarti a cercare i primi a \(\lfloor \sqrt n \rfloor\).
Ho capito una cosa sbagliata che facevo. Invece di andare a verificare se i numeri del vettore sono multipli (uno ad uno) vado direttamente a prendere i multipli.
Intanto ho fatto questo (la trascrizione di wiki)
poi domani/dopodomani gli metterò le migliorie che dici.
Avrei una domanda: quando creo l'array di bool c'è un costruttore diretto che le inizializza tutte a true o devo usare il for?
Grazie
Intanto ho fatto questo (la trascrizione di wiki)
bool A[N+1];
for(int i=0;i<=N; i++) {A[i]=true;}
for(int i=2; i<=N/2; i++){
if(A[i]==true){
for(int j = 2*i; j<=N; j+=i){
A[j]=false;
}
}
}
poi domani/dopodomani gli metterò le migliorie che dici.
Avrei una domanda: quando creo l'array di bool c'è un costruttore diretto che le inizializza tutte a true o devo usare il for?
Grazie
ah era il crivello di Eratostene
forse hai letto una interpretazione o hai applicato alcune proprietà al di fuori del classico crivello, per quello non capivo cosa tu avessi scritto
comunque con le dritte di apatriarca:
mi pare che si possa inizializzare come con lo zero, non ricordo, prova così:
Sì può limitare il ciclo al valore limite floor(sqrt(N)) $\lfloor \sqrt(N) \rfloor$, invece che ad $N/2$.
e non capisco perchè controlli nel ciclo esterno se un valore è primo, devi farlo all'interno se no non ciclerai mai...
poi il ciclo annidato mi pare sbagliato. Non devi sommare, ma moltiplicare $j$.
Vedila così:
mi sembra che anche se si controllasse che un dato valore è true o false (nel setaccio) riassegnarlo ha la stessa complessità... Nel senso che ad ogni ciclo si riasseggna il valore false ai multipli ha la stessa complessità che controllare ogni volta che sia true o false con un if, ed assegnare false.
comunque se vuoi rendere più chiaro il codice così verrebbe:
mi pare che così possa funzionare, controlla, se hai dubbi su cosa sia stato fatto basta chiedere.
PS: non mi convince l'assegnazione di false, forse si può migliorare, ma ora non vedo altro che il cuscino
EDIT: leggere il post di apatriarca sotto.
forse hai letto una interpretazione o hai applicato alcune proprietà al di fuori del classico crivello, per quello non capivo cosa tu avessi scritto
comunque con le dritte di apatriarca:
bool A[N+1];
for(int i=0;i<=N; i++) {A[i]=true;}mi pare che si possa inizializzare come con lo zero, non ricordo, prova così:
bool A[N+1] = {true};for(int i=2; i<=N/2; i++){
if(A[i]==true){
for(int j = 2*i; j<=N; j+=i){
A[j]=false;
}
}
}Sì può limitare il ciclo al valore limite floor(sqrt(N)) $\lfloor \sqrt(N) \rfloor$, invece che ad $N/2$.
e non capisco perchè controlli nel ciclo esterno se un valore è primo, devi farlo all'interno se no non ciclerai mai...
poi il ciclo annidato mi pare sbagliato. Non devi sommare, ma moltiplicare $j$.
Vedila così:
for(int i=2; i<=floor(sqrt(N)); i++){
for(int j = i; j<=N; j++){
A[j*i]=false;
}
}mi sembra che anche se si controllasse che un dato valore è true o false (nel setaccio) riassegnarlo ha la stessa complessità... Nel senso che ad ogni ciclo si riasseggna il valore false ai multipli ha la stessa complessità che controllare ogni volta che sia true o false con un if, ed assegnare false.
comunque se vuoi rendere più chiaro il codice così verrebbe:
for(int i=2; i<=floor(sqrt(N)); i++){
for(int j = i; j<=N; j++){
if(!A[j*i]){
A[j*i]=false;
}
}
}mi pare che così possa funzionare, controlla, se hai dubbi su cosa sia stato fatto basta chiedere.
PS: non mi convince l'assegnazione di false, forse si può migliorare, ma ora non vedo altro che il cuscino
EDIT: leggere il post di apatriarca sotto.
@hamming_burst: Il test al di fuori del ciclo esterno è corretto in quanto si riducono di molto i cicli interni. Il test interno è invece spesso abbastanza inutile in quanto non modifica seriamente la complessità computazionale. Inoltre il test è più costoso computazionalmente della semplice assegnazione per cui non solo non guadagni niente, ma in realtà ottieni un codice che è possibilmente più lento. Per quanto riguarda l'eliminazione dei multipli, si parte spesso dal valore \(i^2\) in quando qualsiasi altro multiplo che lo precede è un multiplo di almeno un primo minore di \(i\). Questo non è in generale garantito per altri valori, anche se si può pensare di eliminare i multipli pari (o anche quelli multipli di 3) se lo si desidera. In effetti, si riduce spesso lo spazio richiesto dall'algoritmo alla metà (o meno ripetendo questo procedimento per i multipli di 3 o addirittura 5) considerando solo i numeri dispari. L'algoritmo non cambia molto e si risparmia un po' di spazio e qualche calcolo. Eliminare anche i multipli di 3, e quindi considerare solo numeri uguali a \( 1 \mod 6 \) o \(5 \mod 6\) è un po' più complicato, ma fattibile. Ma queste sono ottimizzazioni avanzate che per il momento non credo valga la pena di considerare.
ciao apatriarca
ah ok, mi pare accettabile.
grazie della conferma
ok, non avevo considerato proprietà oltre il crivello stesso perciò ho pensato ci fosse qualcosa di sbagliato. Grazie della spiegazione
Perciò ciò che DajeForte ha fatto è corretto.
Il test al di fuori del ciclo esterno è corretto in quanto si riducono di molto i cicli interni.
ah ok, mi pare accettabile.
"apatriarca":
@hamming_burst: Il test interno è invece spesso abbastanza inutile in quanto non modifica seriamente la complessità computazionale. Inoltre il test è più costoso computazionalmente della semplice assegnazione per cui non solo non guadagni niente, ma in realtà ottieni un codice che è possibilmente più lento.
grazie della conferma
Per quanto riguarda l'eliminazione dei multipli, si parte spesso dal valore \(i^2\) in quando qualsiasi altro multiplo che lo precede è un multiplo di almeno un primo minore di \(i\). Questo non è in generale garantito per altri valori, anche se si può pensare di eliminare i multipli pari (o anche quelli multipli di 3) se lo si desidera. In effetti, si riduce spesso lo spazio richiesto dall'algoritmo alla metà (o meno ripetendo questo procedimento per i multipli di 3 o addirittura 5) considerando solo i numeri dispari. L'algoritmo non cambia molto e si risparmia un po' di spazio e qualche calcolo. Eliminare anche i multipli di 3, e quindi considerare solo numeri uguali a \( 1 \mod 6 \) o \(5 \mod 6\) è un po' più complicato, ma fattibile. Ma queste sono ottimizzazioni avanzate che per il momento non credo valga la pena di considerare.
ok, non avevo considerato proprietà oltre il crivello stesso perciò ho pensato ci fosse qualcosa di sbagliato. Grazie della spiegazione
Perciò ciò che DajeForte ha fatto è corretto.
for(int i=2; i<=floor(sqrt(N)); i++){
if(A[i]){
for(int j = i*i; j<=N; j+=i){
A[j]=false;
}
}
}
Ecco questo dovrebbe essere corretto.
Hamming_burst nel tuo codice c'era qualche cosa che non andava: ad esempio va fuori indicizzazione con il secondo for.
Da qualche prima prova pare funzioni.
Ho provato a farlo girare fino a 1 milione e due milioni e ci mette tempo 0.
Poi ho provato a farlo con 10 milioni ma mi da segmentation fault. Credo però sia dovuto ai numeri troppo grossi per gli int.
"DajeForte":
Hamming_burst nel tuo codice c'era qualche cosa che non andava: ad esempio va fuori indicizzazione con il secondo for.
ah sì è dovuto al fatto che aumento $j$ ma non controllo la moltiplicazione, facendo un bel overflow sull'array
si dovrebbe mettere un controllo ed un iteratore aggiuntivo:
for(int i=2; i<=floor(sqrt(N)); i++){
for(int j = 1, int d=i;d<=N || j<=N; d=i*(j++)){
A[d]=false;
}
}
Da qualche prima prova pare funzioni.
Ho provato a farlo girare fino a 1 milione e due milioni e ci mette tempo 0.
Poi ho provato a farlo con 10 milioni ma mi da segmentation fault. Credo però sia dovuto ai numeri troppo grossi per gli int.
E' dovuto al numero intero che rappresenta l'indice e al numero di celle, anche se quello è un qualcosa di un po' diverso collegato alla memoria anche se utilizzi dei bool (dimensione 1 byte).
Forse utilizzando array multidimensionali si può sovrastare questo limite, ma la memoria a disposizione non è infinita e già allocando staticamente un array da 1000000 di celle è un mostro. Ci si può pensare a qualcosa di meglio, tipo utilizzare dei file
Un array di 10 milioni di byte non è poi tanto in realtà, sono circa 10MB.. Ma ci spesso limiti sulle dimensioni di array allocati staticamente che puoi creare (lo stack del tuo programma ha spesso una dimensione abbastanza limitata) e credo che il problema sia questo. Per array di dimensioni maggiori fai uso dell'allocazione dinamica della memoria. Puoi inoltre ridurre di 8 volte l'occupazione di memoria usando vector, bitset o una tua implementazione di questa stessa idea. Puoi poi ridurre ancora della metà considerando solo i numeri dispari. Con queste tecniche ridurresti l'occupazione della memoria sotto a 1 MB.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo