Ho scritto due funzioni di esempio:
Codice:
// primi.h
#ifndef PRIMI
#define PRIMI
class Primi
{
public:
bool eratostene(int n);
bool isPrime(int n);
};
#endif
Codice:
#include <iostream>
#include <cmath>
#include "primi.h"
bool Primi::eratostene(int n)
{
if(n == 1 || n == 0 || !(n & 1))
return false;
else if(n == 2)
return true;
int *sieve = new int[n+1];
memset(sieve, 1, sizeof(sieve)*(n+1));
int sqrt_n = sqrt(n) + 1;
for(register int i = 3; i < sqrt_n; i+=2)
{
if(sieve[i] & 1)
{
for(int j = i << 1; j <= n; j += i)
{
sieve[j] ^= sieve[j];
}
}
}
return sieve[n] & 1;
}
bool Primi::isPrime(int n)
{
if(n == 1 || n == 0 || !(n & 1))
return false;
else if(n == 2)
return true;
int sqrt_n = sqrt(n);
register int i = 3;
for(; (n%i) && i <= sqrt_n; i+=2);
return n == i || i > sqrt_n;
}
Nel primo caso, si tratta di una versione modificata del Crivello di Eratostene (esistono anche metodi migliori), che spiegato in due parole consiste nell'eliminare tutti i divisori di un dato numero. Per fare ciò ho settato l'array con N+1 valori a 1, e a partire dal numero 3 elimino (settando a 0) tutti i suoi multipli, così per 5 e così via. Quando accederò quindi all'elemento in posizione n saprò se è uguale a 1 (quindi primo) oppure uguale a 0 (quindi non primo).
Nel secondo caso l'algoritmo è simile al tuo
@fabio93 (ed è il motivo per il quale dicevo che si può evitare il flag; ma esisteranno altri modi sicuramene per giungere a tal fine). L'interruzione del ciclo avviene se la divisione da resto 0 (quindi n è divisibile per i) oppure se i è maggiore della radice quadrata di n. Considerando il valore di
i quindi sei in grado di dire se il numero è primo o no.
Ho usato qualche piccolo "trick" che ad uno alle prime armi può creare qualche perplessità, quindi preferisco chiarire. Ciò che fa
!(n & 1) è l'and bit a bit con il numero 1, e poi ne inverte logicamente il risultato. E' true quando il numero è pari.
Quindi quando scrivo (sieve & 1), è true se il valore è dispari.
L'ultimo, sieve[j] ^= sieve[j], è/era usato a più basso livello con Assembly (ma tutt'ora utilizzato - a loro discrezione - dai compilatori) e serve ad azzerare il contenuto della variabile. :)
