algorytm.org

Implementacja w C#



Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Test pierwszości - test Fermata - Implementacja w C#
Ocena użytkownikóww: *****  / 2
SłabyŚwietny
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.");
		   }
		}
	}
}
Dodaj komentarz