using System; using System.Collections.Generic; namespace PrimeNumbers { class Program { delegate bool delegate_IsPrime(long number); static List primes = new List(1000); static void Main(string[] args) { // Time in ms to test each function long time = 100; TestPrimes(time, IsPrime_each_by_0); TestPrimes(time, IsPrime_each_by_1); TestPrimes(time, IsPrime_each_by_2); TestPrimes(time, IsPrime_each_by_3); Console.WriteLine(); TestPrimes(time, IsPrime_half_by_1); TestPrimes(time, IsPrime_half_by_2); TestPrimes(time, IsPrime_half_by_3); Console.WriteLine(); TestPrimes(time, IsPrime_sqrt_by_1); TestPrimes(time, IsPrime_sqrt_by_2); TestPrimes(time, IsPrime_sqrt_by_3); Console.WriteLine(); primes.Clear(); TestPrimes(time, IsPrime_each_by_P); primes.Clear(); TestPrimes(time, IsPrime_half_by_P); primes.Clear(); TestPrimes(time, IsPrime_sqrt_by_P); } static void TestPrimes(long time, delegate_IsPrime isPrime) { Console.Write(isPrime.Method.Name + " Found: "); Console.WriteLine(FindPrimes(time, isPrime)); } static long FindPrimes(long time, delegate_IsPrime isPrime) { var finishTime = GetTime() + time; long count = 0; long number = 2; do { if (isPrime(number)) ++count; ++number; } while (GetTime() < finishTime); return count; } static long GetTime() { return DateTime.Now.Ticks / 10000; } static bool IsPrime_each_by_0(long number) { int count = 0; for (int i = 1; i <= number; i++) if (number % i == 0) count++; return count == 2; } static bool IsPrime_each_by_1(long number) { for (int i = 2; i < number; i++) if (number % i == 0) return false; return true; } static bool IsPrime_each_by_2(long number) { if(number == 2) return true; if (number % 2 == 0) return false; for (int i = 3; i < number; i += 2) if (number % i == 0) return false; return true; } static bool IsPrime_each_by_3(long number) { if (number == 2) return true; if (number % 2 == 0) return false; int k = 4; for (int i = 3; i < number; i += k) { if (number % i == 0) return false; k = (k == 2) ? 4 : 2; } return true; } static bool IsPrime_half_by_1(long number) { var max = number / 2; for (int i = 2; i < max; i++) if (number % i == 0) return false; return true; } static bool IsPrime_half_by_2(long number) { if (number == 2) return true; if (number % 2 == 0) return false; var max = number / 2; for (int i = 3; i < max; i += 2) if (number % i == 0) return false; return true; } static bool IsPrime_half_by_3(long number) { if (number == 2) return true; if (number % 2 == 0) return false; int k = 4; var max = number / 2; for (int i = 3; i < max; i += k) { if (number % i == 0) return false; k = (k == 2) ? 4 : 2; } return true; } static bool IsPrime_sqrt_by_1(long number) { var sqrt = Convert.ToInt32(Math.Sqrt(number)); for (int i = 2; i < sqrt; i++) if (number % i == 0) return false; return true; } static bool IsPrime_sqrt_by_2(long number) { if (number == 2) return true; if (number % 2 == 0) return false; var sqrt = Convert.ToInt32(Math.Sqrt(number)); for (int i = 3; i < sqrt; i += 2) if (number % i == 0) return false; return true; } static bool IsPrime_sqrt_by_3(long number) { if (number == 2) return true; if (number % 2 == 0) return false; int k = 4; var sqrt = Convert.ToInt32(Math.Sqrt(number)); for (int i = 3; i < sqrt; i += k) { if (number % i == 0) return false; k = (k == 2) ? 4 : 2; } return true; } static bool IsPrime_each_by_P(long number) { foreach(long i in primes) if (number % i == 0) return false; primes.Add(number); return true; } static bool IsPrime_half_by_P(long number) { var max = number / 2; foreach (long i in primes) { if (i >= max) break; if (number % i == 0) return false; } primes.Add(number); return true; } static bool IsPrime_sqrt_by_P(long number) { if (number == 2) return true; if (number % 2 == 0) return false; int k = 4; var sqrt = Convert.ToInt32(Math.Sqrt(number)); foreach (long i in primes) { if (i >= sqrt) break; if (number % i == 0) return false; k = (k == 2) ? 4 : 2; } primes.Add(number); return true; } } }

Prime numbers. Speed test