C# - Algoritmi numerici
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("");
}