Complessità algoritmo numeri primi

Algoritmi
1

Mentre provavo a svolgere degli esercizi che richiedevano la produzione di numeri primi rispettivamente matrice prima e primo permissivo ho utilizzato 2 algoritmi differenti:

  1. Algoritmo pensato da me ma ovviamente già conosciuto: controllo per ogni numero che non sia divisibile per ogni numero primo minore della sua radice quadrata.

  2. Crivello di Eratostene che si è rivelato essere più efficente.

Algoritmo numero 1:

set <int> primi;
void calcola_primi(int numeromassimo)
{
    bool primo=true;
    int valore=5;
    
    primi.insert(2);
    primi.insert(3);
    while(valore<=numeromassimo)
    {
    primo=true;
	for(set<int>::iterator it=primi.begin(); it!=primi.end() && *it<=sqrt(valore);it++)
		if(valore%*it==0)
			primo=false;
    if(primo){
            primi.insert(valore);
        }
    valore+=2;
    }
}

Crivello (ringrazio Spippolino01 per il codice :smile: )

bool primo[38600];
vector <int> v;

void crivello()
{
   for(int i=2; i< 35001; i++)
        primo[i] = true;
   for(int i=2; i<=sqrt(35001); i++)
   {
       if(primo[i])
       {
           for(int j= i+i; j < 35001; j+=i)
           {
               primo[j]=false;
           }
       }
   }
   return;
}

Come detto in precedenza con il crivello è possibile risolvere entrambi i problemi mentre con il primo algoritmo soltanto “matrice prima”, quindi mi sono messo ad anilizzare la complessità

Primo Algoritmo:
$$\sum_{i=0}^n \pi(Sqrt(i))$$
Secondo Algoritmo: con r=sqrt(n)
$$\sum_{i=0}^r n/i$$

Anche se i non assume valori di numeri primi, quindi il range i r= \pi (r)
È corretta?

2

La complessità del crivello dovrebbe essere \mathcal O(N\log \log N).

3

Ma è approssimativa o “dimostrata”?

1 Mi Piace
4

Dovrebbe essere il limite supriore.
Nel crivello noi per ogni numero primo P_i controlliamo tutti i suoi multipli fino a N che sono \frac{N}{P_i}, quindi il numero di operazioni sarà:
$$\frac{N}{2}+\frac{N}{3}+\frac{N}{5}+\frac{N}{7}+\frac{N}{11}+\cdots +\frac{N}{N}= N\biggl(\frac{1}{2}+\frac{1}{3}+\frac{1}{5}+\frac{1}{7}+\frac{1}{11}+\cdots+\frac{1}{N}\biggr)$$
Il secondo fattore è la somma dei reciproci dei primi, tale somma tende a \log\log N quindi la complessità finale diventa \mathcal O(N\log\log N).

2 Mi Piace
5

Ok capito, loglognN rimane un valore quasi invariante no?
Detto questo, come si puo esprimere la complessità del primo algoritmo in notazione O ()

1 Mi Piace
6

Un primo upper bound è \mathcal O(\frac{N\sqrt N}{logN}).
Ci si arriva partendo da N\pi(\sqrt N) > \sum_{i=1}^N{\pi(\sqrt i)} e dal fatto che i primi \leq N sono \approx \frac{N}{logN}

N\pi(\sqrt N) \approx \frac{N\sqrt N}{log \sqrt N} = \mathcal O(\frac{N^{\frac{3}{2}}}{logN})

1 Mi Piace
7

Effettivamente è molto maggiore, grazie dell’aiuto

1 Mi Piace