Crivello di Dirichlet
La seguente formula permette di ricavare quanti sono i divisori del numero intero positivo N:
(1) $ D(N)=sum_(i = 1)^(N)(FLOOR(N/i)-FLOOR((N-1)/i)) $
con $ FLOOR(X)$ = parte intera del numero X
(qualcheduno osserverà, a ragione, che la sommatoria potevo farla tra 1 e $ root(2)(N) $ )
Allora la (1) permette di verificare la ben nota condizione:
$ D(N)=2 hArr $ N è primo
Tiriamo fuori dalla (1) i divisori 1 ed N (quelli di un numero primo), ottenendo:
(2) $ D(N)=2+sum_(i = 2)^(N-1)(FLOOR(N/i)-FLOOR((N-1)/i)) $
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) $ d(i)=FLOOR(N/i)-FLOOR((N-1)/i) $
allora si dimostra che (4):
a) $ d(i)= 0 hArr $ N non è multiplo di i,
b) $ d(i)= 1 hArr $ 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.
(1) $ D(N)=sum_(i = 1)^(N)(FLOOR(N/i)-FLOOR((N-1)/i)) $
con $ FLOOR(X)$ = parte intera del numero X
(qualcheduno osserverà, a ragione, che la sommatoria potevo farla tra 1 e $ root(2)(N) $ )
Allora la (1) permette di verificare la ben nota condizione:
$ D(N)=2 hArr $ N è primo
Tiriamo fuori dalla (1) i divisori 1 ed N (quelli di un numero primo), ottenendo:
(2) $ D(N)=2+sum_(i = 2)^(N-1)(FLOOR(N/i)-FLOOR((N-1)/i)) $
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) $ d(i)=FLOOR(N/i)-FLOOR((N-1)/i) $
allora si dimostra che (4):
a) $ d(i)= 0 hArr $ N non è multiplo di i,
b) $ d(i)= 1 hArr $ 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.
Risposte
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, [tex]\sum_{i=1}^n5 = 5*\sum_{i=1}^n1 = 5*N)[/tex], mentre nella (2) la complessità è 5*N-9 (sono, in termini di operazioni, [tex]1 + \sum_{i=2}^{n-1}5 = 1 + 5*\sum_{i=1}^{n-2}1 =1 + 5*(N-2)[/tex]). 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 [tex]d(i) = FLOOR\left(\dfrac{N}{i}\right) - FLOOR\left(\dfrac{N-1}{i}\right)[/tex]
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.
A me sembra più corretto dire che nella (1) la complessità + 5*N (sono, in termini di operazioni, [tex]\sum_{i=1}^n5 = 5*\sum_{i=1}^n1 = 5*N)[/tex], mentre nella (2) la complessità è 5*N-9 (sono, in termini di operazioni, [tex]1 + \sum_{i=2}^{n-1}5 = 1 + 5*\sum_{i=1}^{n-2}1 =1 + 5*(N-2)[/tex]). 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 [tex]d(i) = FLOOR\left(\dfrac{N}{i}\right) - FLOOR\left(\dfrac{N-1}{i}\right)[/tex]
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.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo