Решето Аткина

c#
  1. public class Atkin
  2.     {
  3.         internal readonly int _limit;
  4.         public bool[] IsPrimes;
  5.  
  6.         public Atkin() { return; }
  7.         public Atkin(int limit)
  8.         {
  9.             _limit = limit;
  10.             FindPrimes();
  11.         }
  12.  
  13.         public void FindPrimes()
  14.         {
  15.             IsPrimes = new bool[_limit + 1];
  16.             double sqrt = Math.Sqrt(_limit);
  17.             if (sqrt < 29301)
  18.             {
  19.                 for (int x = 1; x <= sqrt; x++)
  20.                     for (int y = 1; y <= sqrt; y++)
  21.                     {
  22.                         int x2 = x * x;
  23.                         int y2 = y * y;
  24.                         int n = 4 * x2 + y2;
  25.                         if (n <= _limit && (n % 12 == 1 || n % 12 == 5))
  26.                             IsPrimes[n] ^= true;
  27.  
  28.                         n -= x2;
  29.                         if (n <= _limit && n % 12 == 7)
  30.                             IsPrimes[n] ^= true;
  31.  
  32.                         n -= 2 * y2;
  33.                         if (x > y && n <= _limit && n % 12 == 11)
  34.                             IsPrimes[n] ^= true;
  35.                     }
  36.  
  37.                 for (int n = 5; n <= sqrt; n += 2)
  38.                     if (IsPrimes[n])
  39.                     {
  40.                         int s = n * n;
  41.                         for (int k = s; k <= _limit; k += s)
  42.                             IsPrimes[k] = false;
  43.                     }
  44.             }
  45.             else
  46.             {
  47.                 var limit = (ulong)_limit;
  48.                 for (ulong x = 1; x <= sqrt; x++)
  49.                     for (ulong y = 1; y <= sqrt; y++)
  50.                     {
  51.                         ulong x2 = x * x;
  52.                         ulong y2 = y * y;
  53.                         ulong n = 4 * x2 + y2;
  54.                         if (n <= limit && (n % 12 == 1 || n % 12 == 5))
  55.                             IsPrimes[n] ^= true;
  56.  
  57.                         n -= x2;
  58.                         if (n <= limit && n % 12 == 7)
  59.                             IsPrimes[n] ^= true;
  60.  
  61.                         n -= 2 * y2;
  62.                         if (x > y && n <= limit && n % 12 == 11)
  63.                             IsPrimes[n] ^= true;
  64.                     }
  65.  
  66.                 for (ulong n = 5; n <= sqrt; n += 2)
  67.                     if (IsPrimes[n])
  68.                     {
  69.                         ulong s = n * n;
  70.                         for (ulong k = s; k <= limit; k += s)
  71.                             IsPrimes[k] = false;
  72.                     }
  73.             }
  74.             IsPrimes[2] = true;
  75.             IsPrimes[3] = true;
  76.         }
  77.     }
 
Использование:
  1. Atkin a = new Atkin(2000000);
  2.  
  3. int i = 1000000
  4. while (i < 2000000)
  5. {
  6.     if (a.IsPrimes[i]) Console.WriteLine(i);
  7. }
Выведет все простые числа в диапазоне от 1 000 000 до 20 000 000.
Назад

Реклама

Мы в соцсетях

tw tg yt gt