VBNet.Su - Visual Basic .NET. ASP .NET. Framework .NET.
Список форумов
Общий форум

Скорость алгоритма: "Доктор, что я не так делаю?"

RE: Скорость алгоритма: "Доктор, что я не так делаю?"

Быстрый переход:
RE: Скорость алгоритма: "Доктор, что я не так делаю?"05 января 2009 / 02:02
Skywalker
Пользователь
ку 2.904296875+

вопросов: 0
советов: 0
ответов: 0
комментариев: 5


  1. using System;
  2. using System.Diagnostics;
  3.  
  4. namespace PrimeFinder
  5. {
  6.     class Program
  7.     {
  8.         static void Main(string[] args)
  9.         {
  10.             System.Diagnostics.Stopwatch sw = new Stopwatch();
  11.             sw.Start();
  12.             PrimesEratosthenes prEra = new PrimesEratosthenes(50000000);
  13.             sw.Stop();
  14.             Console.WriteLine(sw.ElapsedTicks.ToString());
  15.             sw.Reset();
  16.             sw.Start();
  17.             PrimesAtkin prAtk = new PrimesAtkin(50000000);
  18.             sw.Stop();
  19.             Console.WriteLine(sw.ElapsedTicks.ToString());
  20.             Console.ReadLine();
  21.         }
  22.     }
  23.  
  24.     public class PrimesEratosthenes
  25.     {
  26.         private bool[] primes;
  27.  
  28.         public PrimesEratosthenes(long MaxLimit)
  29.         {
  30.             Generate(MaxLimit);
  31.         }
  32.  
  33.         protected void Generate(long MaxLimit)
  34.         {
  35.             primes = new bool[MaxLimit+1];
  36.  
  37.             for (long n = 2; n <= MaxLimit; n++)
  38.                 if (!primes[n])
  39.                     for (long i = n * 2; i <= MaxLimit; i += n) primes<em> = true;
  40.         }
  41.     }
  42.  
  43.     public class PrimesAtkin
  44.     {
  45.         private bool[] primes;
  46.  
  47.         public PrimesAtkin(long MaxLimit)
  48.         {
  49.             Generate(MaxLimit);
  50.         }
  51.  
  52.         protected void Generate(long MaxLimit)
  53.         {
  54.             primes = new bool[MaxLimit+1];
  55.  
  56.             primes[2] = true;
  57.             primes[3] = true;
  58.  
  59.             long sqr_lim = (long)(Math.Sqrt((double)MaxLimit));
  60.             long x2, y2, i, j, n;
  61.  
  62.             x2 = 0;
  63.             for (i = 1; i <= sqr_lim; i++)
  64.             {
  65.                 x2 += 2 * i - 1;
  66.                 y2 = 0;
  67.                 for (j = 1; j <= sqr_lim; j++)
  68.                 {
  69.                     y2 += 2 * j - 1;
  70.                     n = 4 * x2 + y2;
  71.                     if (n <= MaxLimit && (n % 12 == 1 || n % 12 == 5)) primes[n] = !primes[n];
  72.  
  73.                     n -= x2;
  74.                     if (n <= MaxLimit && n % 12 == 7) primes[n] = !primes[n];
  75.  
  76.                     n -= 2 * y2;
  77.                     if (i > j && n <= MaxLimit && n % 12 == 11) primes[n] = !primes[n];
  78.                 }
  79.             }
  80.  
  81.             for (i = 5; i <= sqr_lim; i++)
  82.                 if (primes<em>)
  83.                 {
  84.                     n = i * i;
  85.                     for (j = n; j <= MaxLimit; j += n) primes[j] = false;
  86.                 }
  87.         }
  88.     }
  89. }



результат:
эрато: 26902581
аткин: 21265767

но все равно чот медленно, если найдешь в чом дело, напиши, а то аж интересно стало...
..и было сказано:
Спасибо: VB .NET Programmer
Это отдельная страница сообщения форума. Чтобы посмотреть всю ветку, нажмите на эту ссылку.