Mira akiaquí te voy a poner un algoritmo iterativo que hice hace ya algún tiempo:
public bool EsPrimo(int num)
{
int raiz = Math.Sqrt(num);
int cont = 2;
bool esDivisible= false;
bool esPrimo = false;
if(num == 2)
{
esPrimo = true;
}
else
{
while(cont <= raíz && esDivisible == false)
{
if(num % cont == 0)
{
esDivisible = true;
}
cont++;
}
}
if(esDivisible == false)
{
esPrimo = true;
}
return esPrimo;
}
Un ejemplo de llamada sería por ejemplo para saber los primos qué hay entre 22 y 100100:
for(int i = 2; i<= 100; i++)
{
if(esPrimo(i))
{
Console.WriteLine(i.TiString() + " es primo);
}
}