Ocena użytkownikóww: ***** / 2
Nadesłany przez Tomasz Lubiński, 26 kwietnia 2007 01:00
Kod przedstawiony poniżej przedstawia główną część rozwiązania problemu.
Pobierz pełne rozwiązanie.Jeżeli nie odpowiada Ci sposób formatowania kodu przez autora skorzystaj z pretty printer'a i dostosuj go automatycznie do siebie.
fermat_cs/Fermat.cs:
// Test pierwszości - test Fermata
// www.algorytm.org
// Tomasz Lubinski (c) 2007
using System;
namespace fermat_cs
{
/// <summary>
/// Test Fermata.
/// </summary>
class Fermat
{
/// <summary>
/// calculates a^b mod m
/// </summary>
/// <param name="a">a</param>
/// <param name="b">b</param>
/// <param name="m">m</param>
/// <returns>a^b mod m</returns>
private static int power_modulo_fast(int a, int b, int m)
{
int i;
long result = 1;
long x = a%m;
for (i=1; i<=b; i<<=1)
{
x %= m;
if ((b&i) != 0)
{
result *= x;
result %= m;
}
x *= x;
}
return (int)result%m;
}
/// <summary>
/// Fermat test
/// </summary>
/// <param name="n">number to check</param>
/// <param name="k">number of tries</param>
/// <returns>true - probably prime, false - not prime</returns>
private static Boolean FermatTest(int n, int k)
{
int a, i;
Random rand = new Random();
if (n<4)
{
return true;
}
for (i=0; i<k; i++)
{
a = (int)rand.Next(n-2) + 2;
if (power_modulo_fast(a, n-1, n) != 1)
{
return false;
}
}
return true;
}
/// <summary>
/// The main entry point for the application.
/// </summary>
[STAThread]
static void Main(string[] args)
{
int n, k;
Console.WriteLine("Podaj liczbe do sprawdzenia.");
n = int.Parse(Console.ReadLine());
Console.WriteLine("Podaj dokladnosc sprawdzenia.");
k = int.Parse(Console.ReadLine());
if (FermatTest(n, k))
{
Console.WriteLine("Liczba jest prawdopodobnie pierwsza.");
}
else
{
Console.WriteLine("Liczba jest zlozona.");
}
}
}
}