Pagina personale di:
Carlo Vecchio
appunti di C#, R, SQL Server, ASP.NET, algoritmi, numeri
Vai ai contenuti

C# - Algoritmi numerici

C#

Verificare se un numero è un numero primo
   •   Per verificare se un numero è primo, basta provare a dividerlo per tutti i numeri da 2 fino al numero stesso. Ci si ferma non appena si trova un divisore del numero dato, cioè quando la divisione dà resto 0.
   •   In pratica, è sufficiente arrivare a dividere il numero dato, fino alla radice quadrata del numero stesso: infatti il più piccolo divisore di un numero non può essere superiore alla radice quadrata del numero stesso.
   •   La funzione seguente verifica se il numero passato come argomento è primo o no.

   private bool IsPrime(int number)
   {
       
for (int i = 2; i <= Math.Sqrt(number); ++i)
           
if (number % i == 0) return false;
       
return true;
   }

   Console
.WriteLine(IsPrime(34751));   // false 589 * 59
   
Console.WriteLine(IsPrime(4999));    // true

Trovare numeri primi con il Crivello di Eratostene
   •   Il Crivello di Eratostene permette di trovare tutti i numeri primi fino ad un certo numero N prefissato. Questo metodo deve il proprio nome al matematico Eratostene di Cirene, che ne fu l'ideatore.
   •   Il crivello consiste nello scrivere tutti i numeri naturali da 2 a N. Poi si procede ripetutamente prendendo il primo della lista (che è primo) e si cancellano tutti i suoi multipli.
   •   Il primo numero che si considera è quindi 2 e si cancellano dalla lista i suoi multipli (tutti i numeri pari).
   •   Il secondo numero della lista è il 3 e si cancellano tutti i suoi multipli (che non sono ancora stati cancellati).
   •   Il terzo numero della lista è il 5 (il 4 è già stato cancellato) e si cancellano tutti i suoi multipli.
   •   Si termina quando tutti i numeri sono stati considerati "primi" o sono stati cancellati.
   •   La funzione seguente restituisce un array contenente tutti i numeri primi fino a un numero massimo passato come argomento.

   private int[] ElencoPrimi(int maxNumber)
   {
       
// Array di boolean di supporto: num[i] = true se i è primo
       
bool[] num = new bool[maxNumber + 1];

       
// Si inizializza l'array
       
for (int i = 2; i < num.Length; i++)
       {
           num[i] =
true;
       }

       
// Qua c'è il Crivello di Eratostene
       
int index = 2;
       
while (index < num.Length)
       {
           
// Si eliminano tutti i multipli di i
           
int j = 2 * index;
           
while (j < num.Length)
           {
               num[j] =
false;
               j += index;
           }
           
// Si procede fino al successivo elemento di num[] che è true
           index++;
           
while (index < num.Length)
           {
               
if (num[index])
                   
break;
               index++;
           }
       }

       // Si prepara l'array di ritorno
       
int[] ret = new int[0];   // è l'array di ritorno

       
for (int i = 0; i < num.Length; i++)
       {
           
if (num[i])
           {
               
// Se i è primo, lo si aggiunge all'array di ritorno
               
Array.Resize(ref ret, ret.Length + 1);
               ret[ret.Length - 1] = i;
           }
       }

       
return ret;
   }
        
   •   Esempio di utilizzo della funzione 'ElencoPrimi()':

   int
[] numeriPrimi = ElencoPrimi(5000);

Massimo Comun Divisore (Algoritmo di Euclide)
   •   L'algoritmo di Euclide
permette di calcolare il Massimo Comun Divisore tra due numeri in modo molto efficiente.
   •   L'algoritmo si basa sul fatto che il M.C.D. tra due numeri è uguale al M.C.D. tra uno di essi e il resto della loro divisione.
   •   La seguente funzione restituisce il M.C.D. tra i due numeri passati come argomento.

   private int MassimoComunDivisore(int a, int b)
   {
       
int resto;
       
while (b != 0)
       {
           resto = a % b;
           a = b;
           b = resto;
       }
       
return a;
   }

   •   Esempio di utilizzo della funzione MassimoComunDivisore()':

   Console.WriteLine(MassimoComunDivisore(1071, 1029));

Calcolare il fattoriale di un numero
   •   Il fattoriale
di un numero intero, è il prodotto tra il numero stesso e tutti i numeri inferiori ad esso fino a 2 (perché 1 è irrilevante nella moltiplicazione).
   •   Il fattoriale si indica con il punto esclamativo, perciò il fattoriale di 5 si indica con 5! ed è: 5! = 5 * 4 * 3 * 2 = 120.
   •   La funzione seguente calcola il fattoriale del numero passato come argomento.
   •   Per definizione il fattoriale di 0 è 1.

   private static int Fattoriale(int number)
   {
       
if (number < 0)
           
return 0;
       
else if (number <= 1)
           
return 1;
       
else
       {
           
int prod = 1;
           
for (int i = 2; i <= number; i++)
           {
               prod *= i;
           }
           
return prod;
       }
   }


   •   Esempio di utilizzo della funzione Fattoriale()':

   Console.WriteLine(Fattoriale(5));

Fattorizzazione di un numero
   •   Fattorizzare
un numero significa scomporlo nel prodotto di numeri primi. Per esempio il numero 24 si scompone nel modo seguente: 24 = 2^3 * 3. I fattori di 24 sono quindi 2 e 3.
   •   Ogni numero ha un'unica fattorizzazione in numeri primi; si veda il Teorema Fondamentale dell'Aritmetica
.
   •   Un modo per fattorizzare un numero, consiste nel dividere il numero stesso per i numeri primi 'possibili' divisori e verificare se il resto della divisione è nullo.
   •   La funzione seguente fattorizza il numero passato come primo argomento e restituisce un array di interi contenente i fattori. Il secondo parametro consente di ottenere tutti i fattori anche ripetuti oppure i soli fattori distinti. La funzione necessita della funzione 'ElencoPrimi()' sopra descritta.

   private int[] Fattorizzazione(int number, bool completa)
   {
       
// Restituisce tutti i fattori del numero dato.
       
//    Parametro 'completa' = true, ogni fattore è restituito
       //                           tante volte quante volte compare nella fattorizzazione

       
//                         = false, ogni fattore è restituito una sola volta
       
int[] ret = new int[0];

       
if (number < 2)
           
return ret;

       
// Si calcolano tutti i numeri primi che possono dividere 'number'
       
int[] primi = ElencoPrimi(Convert.ToInt32(Math.Sqrt(number)));

       
for (int i = 0; i < primi.Length; i++)
       {
           
if (number % primi[i] == 0)
           {
               
// primi[i] è un fattore
               
if (completa || (!completa && ret.Length == 0)
                            || (!completa && ret.Length > 0 && ret[ret.Length - 1] != primi[i]))
               {
                   
Array.Resize(ref ret, ret.Length + 1);
                   ret[ret.Length - 1] = primi[i];
               }
               number /= primi[i];
               
if (number == 1)
                   
break;
               
// Si riprova con lo stesso divisore
               i--;  
           }
       }
       
// Si aggiunge l'ultimo fattore rimasto
       
if (number != 1)
       {
           
if (completa || (!completa && ret.Length == 0)
                        || (!completa && ret.Length > 0 && ret[ret.Length - 1] != number))
           {
               
Array.Resize(ref ret, ret.Length + 1);
               ret[ret.Length - 1] = number;
           }
       }

       
return ret;
   }

   •   Nell'esempio seguente si utilizza la funzione 'Fattorizzazione()' per fattorizzare i numeri fino a 100.

   for (int i = 0; i < 101; i++)
   {
       
Console.WriteLine("Fattori di " + i + ": ");

       
int[] f1 = Fattorizzazione(i, true);
       
for (int j = 0; j < f1.Length; j++)
       {
           
Console.Write(f1[j].ToString() + " ");
       }
       
Console.WriteLine("");

       
int[] f2 = Fattorizzazione(i, false);
       
for (int j = 0; j < f2.Length; j++)
       {
           
Console.Write(f2[j].ToString() + " ");
       }
       
Console.WriteLine("");
   }

© 2020 Carlo Vecchio
Torna ai contenuti