Nu aveti permisiuni pentru a descarca fisierul grader_test2.ok
Diferente pentru ciurul-lui-eratostene intre reviziile #6 si #7
Nu exista diferente intre titluri.
Diferente intre continut:
O prima idee de optimizare ar fi sa nu mai luam in calcul numerele pare pentru ca stim ca singurul numar prim par e {$2$}. Deci sa vedem noua varianta a programului:
p(pre). {@ //class PrimeNumbersSieve2@}
{@ final int MAXSIZE = 1000001;@}
{@ char[] p = new char[MAXSIZE];@}
{@ @}
{@ //p[i] == 0 if i is prime@}
{@ @}
{@ public int getTheNumber(int n) {@}
{@ int i, j, nr = 1;@}
{@ for (i = 3; i <= n; i += 2) {@}
{@ if (p[i] @}=={@ 0) {@}
{@ nr++;@}
{@ for (j = i + i + i; j <= n; j += i << 1) {@}
{@ p[j] = 1;@}
{@ }@}
{@ }@}
{@ }@}
{@ return nr;@}
{@ }@}
== code(java) |
//class PrimeNumbersSieve2
final int MAXSIZE = 1000001;
char[] p = new char[MAXSIZE];
//p[i] == 0 if i is prime
public int getTheNumber(int n) {
int i, j, nr = 1;
for (i = 3; i <= n; i += 2) {
if (p[i] == 0) {
nr++;
for (j = i + i + i; j <= n; j += i << 1) {
p[j] = 1;
}
}
}
return nr;
}
==
Putem incerca o optimizare de memorie, pentru ca nu mai avem nevoie de elementele cu index par din sirul {$p$}. Acum semnificatia lui $p{~i~}$ s-a schimbat $p{~i~}$ fiind 0 daca $2*i+1$ e numar prim si $1$ daca nu.
p(pre). {@ // class PrimeNumbersSieve3 @}
{@ final int MAXSIZE = 1000000/2+1;@}
{@ char[] p = new char[MAXSIZE];@}
{@ @}
{@ //p[i] @}=={@ 0 if 2*i + 1 is prime@}
{@ @}
{@ public int getTheNumber(int n) {@}
{@ int i, j, nr = 1;@}
{@ for (i = 1; (i << 1) + 1 <= n; i += 1) {@}
{@ if (p[i] @}=={@ 0) {@}
{@ nr++;@}
{@ for (j = i + i + i + 1; (j << 1) + 1 <= n; j += (i << 1) + 1) {@}
{@ p[j] = 1;@}
{@ }@}
{@ }@}
{@ }@}
{@ return nr;@}
{@ }@}
== code(java) |
// class PrimeNumbersSieve3
final int MAXSIZE = 1000000/2+1;
char[] p = new char[MAXSIZE];
//p[i] == 0 if 2*i + 1 is prime
public int getTheNumber(int n) {
int i, j, nr = 1;
for (i = 1; (i << 1) + 1 <= n; i += 1) {
if (p[i] == 0) {
nr++;
for (j = i + i + i + 1;
(j << 1) + 1 <= n;
j += (i << 1) + 1) {
p[j] = 1;
}
}
}
return nr;
}
==
Urmatoarea optimizare va fi marcarea multiplilor numarului prim $i$ de la $i*i$ nu de la $2*i$ cum am facut in prima varianta sau de la $3*i$ cum am facut in a {$2$}-a. Aceasta optimizare este evidenta: orice numar prim compus multiplu de $i$ mai mic decat $i*i$ are un factor prim mai mic decat {$i$}, si acel factor l-a marcat mai devreme, deci nu are rost sa il marcam si la pasul {$i$}. Ideea aceasta este exact ideea ce se foloseste la rezolvarea problemei "Numere Prime":http://www.infoarena.ro/task/prim din arhiva infoarena. Sa vedem acum codul sursa:
