PDA

View Full Version : Numero primo

GiulioCesare
14-04-2005, 20:04
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
14-04-2005, 21:07
Puoi modificare il ciclo for così:


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 :D
lombardp
14-04-2005, 21:14
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
14-04-2005, 21:14
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
14-04-2005, 21:15
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 :D
Poco in confronto al resto se lo fai una volta sola...
71104
14-04-2005, 21:41
in realtà potresti mettere j<radq(n) ma non ho idea del tempo che occorre a calcolare la radice quadrata :D
pochi cicli di clock: la FPU deve solo dividere l'esponente per 2.
cionci
14-04-2005, 21:44
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
14-04-2005, 21:52
mi raccomando non scoprite maniere troppo efficienti perchè altrimenti ritorniamo al medioevo della crittografia :read: :D
cionci
14-04-2005, 22:00
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
14-04-2005, 22:01
mi raccomando non scoprite maniere troppo efficienti perchè altrimenti ritorniamo al medioevo della crittografia :read: :D
No stai tranquillo, il mio algoritmo lo tengo segretissimo :D
71104
15-04-2005, 09:04
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... :mbe:
*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... :O
71104
15-04-2005, 09:10
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
15-04-2005, 09:14
hmmm, questo non mi torna... :mbe:
*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... :O
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
15-04-2005, 12:58
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) ;)
:doh::muro::cry::mc:
che figura... :stordita::D
^TiGeRShArK^
16-04-2005, 12:05
me la ricordo la discussione del crivello di eratostene! :D:D:D
bellissima!!! :sofico:
71104
16-04-2005, 13:13
me la ricordo la discussione del crivello di eratostene! :D:D:D
bellissima!!! :sofico:
asd, noi alla Sapienza (dipartimento di Informatica) al corso di programmazione I abbiamo fatto un homework sul crivello di Eratostene :D
il mio ce l'ho ancora se volete :D