Guest User

Quadratic primes test

a guest
Apr 19th, 2013
77
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Text;
  4. using System.Diagnostics;
  5. using System.Linq;
  6.  
  7. namespace ConsoleApplication1
  8. {
  9.     class Program
  10.     {
  11.         static Primes primes;
  12.         class Primes
  13.         {
  14.             public HashSet<int> all_numbers = new HashSet<int>();
  15.             public HashSet<int> list_of_primes = new HashSet<int>();
  16.             public HashSet<int> list_of_nonprimes = new HashSet<int>();
  17.  
  18.  
  19.             public Primes(int n)
  20.             {
  21.                 all_numbers = new HashSet<int>(Enumerable.Range(1, n));
  22.                 for (int i = 2; i < Math.Sqrt(n) + 1; i++)
  23.                 {
  24.                     for (int j = 3; j <= n / i; j++)
  25.                         list_of_nonprimes.Add(i * j);
  26.                 }
  27.                 list_of_primes = new HashSet<int>(all_numbers.Except(list_of_nonprimes));
  28.             }
  29.  
  30.         }
  31.  
  32.         static void Main(string[] args)
  33.         {
  34.             Stopwatch t = new Stopwatch();
  35.             t.Reset();
  36.             t.Start();
  37.             Console.WriteLine(FindMaxCoeff());
  38.             t.Stop();
  39.             Console.WriteLine(t.ElapsedMilliseconds);
  40.             t.Start();
  41.             primes = new Primes(1000);
  42.             Console.WriteLine(FindMaxCoeff2());
  43.             t.Stop();
  44.             Console.WriteLine(t.ElapsedMilliseconds);
  45.             Console.ReadKey();
  46.         }
  47.  
  48.         static int FindMaxCoeff()
  49.         {
  50.             int maxConsec = 0;
  51.             int maxCoeff = 0;
  52.             for (int a = -999; a < 1000; a++)
  53.             {
  54.                 for (int b = -999; b < 1000; b++)
  55.                 {
  56.                     int currentConsec = FindMaxConsecutive(a, b);
  57.                     if (currentConsec > maxConsec)
  58.                     {
  59.                         maxConsec = currentConsec;
  60.                         maxCoeff = a * b;
  61.                     }
  62.                 }
  63.             }
  64.  
  65.             return maxCoeff;
  66.         }
  67.  
  68.         static int FindMaxConsecutive(int a, int b)
  69.         {
  70.             int n = 0;
  71.  
  72.             for (n = 0; IsPrime(n * n + a * n + b); n++) ;
  73.  
  74.             return n;
  75.         }
  76.  
  77.         static bool IsPrime(int n)
  78.         {
  79.             n = Math.Abs(n);
  80.             if (n == 1 || n == 2 || n == 3)
  81.             {
  82.                 return true;
  83.             }
  84.  
  85.             if (n % 2 == 0 || n % 3 == 0)
  86.             {
  87.                 return false;
  88.             }
  89.  
  90.             for (int x = 6; x - 1 <= Math.Sqrt(n); x += 6)
  91.             {
  92.                 if (n % (x - 1) == 0 || n % (x + 1) == 0)
  93.                 {
  94.                     return false;
  95.                 }
  96.             }
  97.  
  98.             return true;
  99.         }
  100.  
  101.         static int FindMaxCoeff2()
  102.         {
  103.             int maxConsec = 0;
  104.             int maxCoeff = 0;
  105.             for (int a = -999; a < 1000; a++)
  106.             {
  107.                 for (int b = -999; b < 1000; b++)
  108.                 {
  109.                     int currentConsec = FindMaxConsecutive2(a, b);
  110.                     if (currentConsec > maxConsec)
  111.                     {
  112.                         maxConsec = currentConsec;
  113.                         maxCoeff = a * b;
  114.                     }
  115.                 }
  116.             }
  117.  
  118.             return maxCoeff;
  119.         }
  120.  
  121.         static int FindMaxConsecutive2(int a, int b)
  122.         {
  123.             int n = 0;
  124.  
  125.             for (n = 0; primes.list_of_primes.Contains(n * n + a * n + b); n++) ;
  126.  
  127.             return n;
  128.         }
  129.          
  130.     }
  131. }
RAW Paste Data