Crivello di Dirichlet

[lukul]

La seguente formula permette di ricavare quanti sono i divisori del numero intero positivo N:

(1) \( \displaystyle {D}{\left({N}\right)}={\sum_{{{i}={1}}}^{{{N}}}}{\left({F}{L}{O}{O}{R}{\left(\frac{{N}}{{i}}\right)}-{F}{L}{O}{O}{R}{\left(\frac{{{N}-{1}}}{{i}}\right)}\right)} \)

con \( \displaystyle {F}{L}{O}{O}{R}{\left({X}\right)} \) = parte intera del numero X

(qualcheduno osserverà, a ragione, che la sommatoria potevo farla tra 1 e \( \displaystyle {\sqrt[{{2}}]{{{N}}}} \) )

Allora la (1) permette di verificare la ben nota condizione:

\( \displaystyle {D}{\left({N}\right)}={2}\Leftrightarrow \) N è primo

Tiriamo fuori dalla (1) i divisori 1 ed N (quelli di un numero primo), ottenendo:

(2) \( \displaystyle {D}{\left({N}\right)}={2}+{\sum_{{{i}={2}}}^{{{N}-{1}}}}{\left({F}{L}{O}{O}{R}{\left(\frac{{N}}{{i}}\right)}-{F}{L}{O}{O}{R}{\left(\frac{{{N}-{1}}}{{i}}\right)}\right)} \)

Se il nostro numero N è primo, la sommatoria che compare nella (2) ovviamente essere nulla.

Prendiamo un termine generico della sommatoria che compare nella (2):

(3) \( \displaystyle {d}{\left({i}\right)}={F}{L}{O}{O}{R}{\left(\frac{{N}}{{i}}\right)}-{F}{L}{O}{O}{R}{\left(\frac{{{N}-{1}}}{{i}}\right)} \)

allora si dimostra che (4):

a) \( \displaystyle {d}{\left({i}\right)}={0}\Leftrightarrow \) N non è multiplo di i,
b) \( \displaystyle {d}{\left({i}\right)}={1}\Leftrightarrow \) N è multiplo di i.

Il crivello di Dirichlet è tuttavia computazionalmente più costoso di quello di Eratostene,
in quanto per calcolare ogni termine (3) della sommatoria che compare nella (2) occorre fare ben 5 operazioni.
In totale per stabilire se N è primo , se si utilizza la (2), occorre fare 5*(N-2)+1+(N-3) operazioni rispetto alle
5*N+N-1 operazioni della (1).
Al crescer di N tale metodo è poco efficiente.
Qualcuno ha dei suggerimenti per velocizzare i calcoli, magari evitando di effettuare il riscontro
espresso nella (4) per ogni d(i) ?

In attesa di una vostra cortese risposta, vogliate gradire i miei più cordiali saluti.

[canemacchina]

Scusa una cosa, solo una precisazione: come hai calcolato le complessità?
A me sembra più corretto dire che nella (1) la complessità + 5*N (sono, in termini di operazioni, \( \displaystyle \sum_{i=1}^n5 = 5*\sum_{i=1}^n1 = 5*N) \) , mentre nella (2) la complessità è 5*N-9 (sono, in termini di operazioni, \( \displaystyle 1 + \sum_{i=2}^{n-1}5 = 1 + 5*\sum_{i=1}^{n-2}1 =1 + 5*(N-2) \) ). Il che mi torna anche a logica. Ogni temine della sommatoria costa 5 operazioni, la (2) rispetto alla (1) esegue 2 termini in meno (quindi 10 operazioni in meno) ma aggiunge una somma finale (1 operazione in più), quindi rispetto alla complessità 5*N della (1) la (2) costa 5*N + 10 - 1 = 5*N-9.

Poi, tornando alla discussione vera:
ok, non conoscevo questo crivello, ma mi ha incuriosito. Però non capisco: perché eseguire \( \displaystyle d(i) = FLOOR\left(\dfrac{N}{i}\right) - FLOOR\left(\dfrac{N-1}{i}\right) \)
e testare se d(i) = 0 o 1 per sapere se N è multiplo di i??
Alla fine quello che stai facendo non è altro che testare, per ogni i, se N è multiplo di i o no, ovvero basta eseguire il modulo di N rispetto ad i.
Se vale 0, allora N è multiplo di i, se non vale 0 allora N non è multiplo di i.
C'è un motivo per cui FLOOR costa meno di MOD??? Io non credo.

Alla fine questo crivello conta i divisori di N provando se ogni i tra 1 e N lo divide o meno... Servono esattamente N passi.