Numero primo

[GiulioCesare]

Salve ragazzi sto facendo una funzione in C++ che mi calcoli se un numero è primo, oppure no. Ho usato un metodo iterativo, che controlla il numero per quali numeri è divisibile, partendo da 2 fino ad arrivare al numero stesso. Questa maniera piò risultare efficace se il numero in questione è piccolo, ma è una soluzione lentissima se il numero è grande. Comunque posto la mia funzione, in attesa che qualcuno mi voglia dare una mano.

bool calcolo(int n)
{
for (int j=2; j<n; j++)
{

if (!n%j)
return false;
}
return true;
}

[Zhurlo]

Puoi modificare il ciclo for così:

Originariamente inviato da GiulioCesare

for (int j=2; j<n/2; j++)

in realtà potresti mettere j<radq(n) ma non ho idea del tempo che occorre a calcolare la radice quadrata

[lombardp]

Originariamente inviato da GiulioCesare

Salve ragazzi sto facendo una funzione in C++ che mi calcoli se un numero è primo, oppure no. Ho usato un metodo iterativo, che controlla il numero per quali numeri è divisibile, partendo da 2 fino ad arrivare al numero stesso. Questa maniera piò risultare efficace se il numero in questione è piccolo, ma è una soluzione lentissima se il numero è grande. Comunque posto la mia funzione, in attesa che qualcuno mi voglia dare una mano.

bool calcolo(int n)
{
for (int j=2; j<n; j++)
{

if (!n%j)
return false;
}
return true;
}

Ci sono montagne di algoritmi più o meno veloci per determinare se un numero è primo, però tutti sono estremamente lenti al crescere del numero stesso. Anzi è uno dei più grandi problemi irrisolti della matematica: dato l'n° numero primo, determinare l' (n+1)°.

Comunque, inserisci le keywords "primality algorythm" o "primality algorithm".

Per tornare all'atto pratico, puoi dimezzare il tempo del tuo algoritmo riducendo il ciclo fino a n/2... tanto è uguale! (Edit: Zhurlo è arrivato prima di me...)

Un algoritmo storico è il "crivello di Eratostene", ideato nel 240 a.C.
http://www.vialattea.net/esperti/mat/primi/crivell.html

[cionci]

C'è tutta una teoria matematica dietro che non ti immagini nemmeno
Tempo fa c'eravamo messi tutti a cercare un modo un po' più veloce per generare in numeri primi fra 1 e N...ma ti assicuro che è un bel casotto...

Tanto per cominciare...non importa calcolare il for con il limite di n...ma basta limitare la ricerca a sqrt(n)...

int lim = sqrt(n);
for (int j=2; j<=lim; j++)

Infatti se esiste m > lim tale che n è divisibile per m, allora n = m * q, ma ciò implica q < lim...quindi se n non fosse primo lo avresti già scoperto testando q...

[cionci]

Originariamente inviato da Zhurlo

Puoi modificare il ciclo for così:
in realtà potresti mettere j<radq(n) ma non ho idea del tempo che occorre a calcolare la radice quadrata

Poco in confronto al resto se lo fai una volta sola...

[71104]

Originariamente inviato da Zhurlo

in realtà potresti mettere j<radq(n) ma non ho idea del tempo che occorre a calcolare la radice quadrata

pochi cicli di clock: la FPU deve solo dividere l'esponente per 2.

[cionci]

Ah, mi ero dimenticato:


if (!n%2)
return false;

int lim = sqrt(n);

for (int j=3; j<lim; j+=2)
{

if (!n%j)
return false;
}

[kingv]

mi raccomando non scoprite maniere troppo efficienti perchè altrimenti ritorniamo al medioevo della crittografia

[cionci]

Originariamente inviato da 71104

pochi cicli di clock: la FPU deve solo dividere l'esponente per 2.

Non basta...deve essere fatta anche la radice quadrata della mantissa... Il discorso che fai tu è valido solo per potenze di 2...

[cionci]

Originariamente inviato da kingv

mi raccomando non scoprite maniere troppo efficienti perchè altrimenti ritorniamo al medioevo della crittografia

No stai tranquillo, il mio algoritmo lo tengo segretissimo

[71104]

Originariamente inviato da cionci

Non basta...deve essere fatta anche la radice quadrata della mantissa... Il discorso che fai tu è valido solo per potenze di 2...

hmmm, questo non mi torna...
*INCREDIBILE, STO PENSANDO!!!*

sqrt(pow(x, 6)) == pow(x, 3);
ecco, questo mi torna!

quanto fa radice quadrata di x alla 6? x alla 3! lei mi cade sulle basi signor cionci...

[71104]

esempio pratico: prendiamo x uguale che ne so, 3!
3 alla 6 = 729
3 alla 3 = 27
radice di 3 alla 6 = 27
3 alla 3 = radice di 3 alla 6
cvd

[cionci]

Originariamente inviato da 71104

hmmm, questo non mi torna...
*INCREDIBILE, STO PENSANDO!!!*

sqrt(pow(x, 6)) == pow(x, 3);
ecco, questo mi torna!

quanto fa radice quadrata di x alla 6? x alla 3! lei mi cade sulle basi signor cionci...

Peccato che il formato IEEE754 non sia m^e, ma m * 2^e...quindi tenendo lo stesso m....sqrt(m * 2^e) = sqrt(m) * 2^(e/2) != m * 2^(e/2)

[71104]

Originariamente inviato da cionci

Peccato che il formato IEEE754 non sia m^e, ma m * 2^e...quindi tenendo lo stesso m....sqrt(m * 2^e) = sqrt(m) * 2^(e/2) != m * 2^(e/2)

che figura...

[^TiGeRShArK^]

me la ricordo la discussione del crivello di eratostene!
bellissima!!!

[71104]

Originariamente inviato da ^TiGeRShArK^

me la ricordo la discussione del crivello di eratostene!
bellissima!!!

asd, noi alla Sapienza (dipartimento di Informatica) al corso di programmazione I abbiamo fatto un homework sul crivello di Eratostene
il mio ce l'ho ancora se volete