I numeri primi sono tutti i numeri naturali divisibili solo per 1 e per se stessi.

Formula

Se avessi trovato una formula per calcolare i numeri primi non penso che avrei un blog. Molto più probabilmente starei a bermi un Negroni alle Fiji.

Non esiste al momento una formula che sia in grado di calcolarli. Anzi, è dimostrato che non esiste un polinomio generatore di numeri esclusivamente primi, nonostante ci siano molti polinomi che sono in grado di generare molti numeri primi. Per capirci una cosa tipo:

\sum\limits_{i=0}^n a_ix^i=a_nx^n+a_{n-1}x^{n-1}+...+a_0

se inseriamo i valori n=2, a_i=\{41,1,1\} diventa

x_2+x+41

che per 0<=x<=39 è effettivamente un numero primo. Se provate però x=40 la magia finisce.

Niente formula, niente funzione. Però, anche se non possiamo generarli così su due piedi, possiamo fare qualcosa.

Test di primalità

Possiamo capire se un numero $p è primo. E questo è banale. Basta dividerlo per tutti i numeri da 1 a $p e segnarsi come va, in accordo con la definizione. Per calcolare il resto della divisione si usa l’operatore modulo %.

Possiamo però ottimizzare il codice evitando conti inutili. Non ha senso testare divisori più grandi della radice di $p perché il risultato della divisione sarebbe sicuramente un numero più piccolo della radice di $p. Dato che il quoziente e il divisore sono intercambiabili in una divisione, se fosse un divisore intero l’avremmo sicuramente già provato.

Ora prova tu

Scegli 1 < p < 108 e controlla se è primo.

<?php
function isPrime($p, &$i) {
  	for ($i = 2; $i <= sqrt($p); $i++) {
      if (!($p % $i)) return false;
    }
  
	return true;
}


$IN = (array) json_decode(base64_decode($argv[1]));
extract($IN);
$isPrime = isPrime($p, $i);
echo $p.($isPrime ? "" : " non")." è primo\n";
if (!$isPrime) {
 echo "Prova a dividerlo per $i";
}
?>

Input in formato JSON

{ 
  "p": 7
}
7 è primo

Il crivello di Eratostene

Un modo veloce per trovare tutti i fattori primi da 1 a $n potrebbe essere testarli tutti tramite la funzione che abbiamo scritto prima. Il test di primalità viene eseguito però sempre da 1 a $p per ogni $p testato, con un’evidente ripetizione di calcoli.

Eratostene di Cirene, matematico dell’antica Grecia, guardò il problema da un’altra prospettiva. Se mettiamo in una tabella tutti i numeri (da qui il nome crivello che significa setaccio) capiamo subito che non c’è bisogno di testare alcunché se si cambia la domanda da “$p è primo?” a “$p è multiplo?”.

Crivello di Eratostene

Il nostro programma non dovrà fare altro che, partendo da 2, eliminare tutti i multipli fino a $n di ogni numero che incontra. Quando individua un numero non eliminato, ciò implica il fatto che sia primo.

credits immagine: Wikipedia

Fattori primi

I fattori primi di un numero sono tutti i divisori del numero che sono primi.

Anche qui potremmo calcolarli con il test di primalità su tutti i numeri da 1 a N (o alla sua radice). Possiamo perfezionare questo metodo dividendo ogni volta per il fattore trovato. In questo modo otteniamo un numero più piccolo ma con gli stessi divisori del precedente, diminuendo di molto il tempo di calcolo.

Ora prova tu

Scegli 1 < N < 108 e trova tutti i suoi fattori primi.

<?php

function fattoriPrimi($N) {
 	$p = []; //fattori primi di $N. 
    $j = 2; //test dei divisori
    
    while($j <= sqrt($N)) {
        //Se è un divisore
        while(!($N % $j)) {
            //Divido per il divisore
            $N /= $j;                 
            $p[$j] = 1;
        }     
        $j++;        
    }
  //Aggiungo quoziente $N se diverso da 1 perché anch'esso è un divisore primo
  if ($N > 1) $p[$N] = 1; 
  return array_keys($p);
}

$IN = (array) json_decode(base64_decode($argv[1]));
extract($IN);
$f = fattoriPrimi($N);

echo implode("\n", $f);

?>

Input in formato JSON

{ 
  "N": 20
}
2
5

Il prossimo passo è trovare tutti i suoi divisori.

0 0 votes
Article Rating
Notifiche
Notificami
0 Commenti
Inline Feedbacks
View all comments