[Java] Numeri primi

[marcusbasic]

Ho il seguente codice java che trova i numeri primi, ma non riesco proprio a capirlo. Chi di buona volontà me lo spiega?

Grazie.

-----

static void NumPrimi0(int n)
{
int cnt = 0;
int[]np=new int[n*n+1];

for(int i = 0; i <= n * n; i++)
np[i] = i;

for(int i=2;i<=n;i++)
{
if (np[i] != 0)
{
for(int j = 2 * i; j <= n * n; j = j + i)
np[j] = 0;
}
}

for(int i = 2; i <= n * n; i++)
{
if (np[i] != 0) {
System.out.printf("%10d", i);

if (++cnt >= 10) {
System.out.println();
cnt = 0;
}
}
}
}

[LeleFT]

Java viene trattato nell'apposito sub-forum.


Ti sposto.


Ciao.

[doraemon83]

molto semplicemente inizializza un array con tutti i numeri da 0 a n*n in ordine crescente.

Dopodiché per ogni valore contenuto nell'array, scandisce tutto l'array accedendo alle locazioni in cui ci sono tutti i multipli di quel numero e li mette a 0 in quanto sicuramente non sono numeri primi. e fa questo per tutti i numeri dell'array.

in ogni caso questo algoritmo fa un notevole spreco di memoria, in quanto utilizza n*n locazioni, che in realtà non sono necessarie. Lui le utilizza in quanto nel ciclo interno lui elimina tutti i multipli di tutti i numeri da 1 a n (anche tutti i multipli di n), in modo da non incorrere in accessi fuori range.

Questa è una versione non ottimizzata del crivello di Erastotene, un algoritmo appunto per trovare tutti i numeri primi minori di un certo valore.

Guarda qui :

Numeri primi