{"id":312881,"date":"2020-11-10T09:00:55","date_gmt":"2020-11-10T09:00:55","guid":{"rendered":"http:\/\/savepearlharbor.com\/?p=312881"},"modified":"-0001-11-30T00:00:00","modified_gmt":"-0001-11-29T21:00:00","slug":"","status":"publish","type":"post","link":"https:\/\/savepearlharbor.com\/?p=312881","title":{"rendered":"\u0418\u0449\u0435\u043c \u043f\u0440\u043e\u0441\u0442\u044b\u0435 \u0447\u0438\u0441\u043b\u0430 \u0434\u043e \u0442\u0440\u0438\u043b\u043b\u0438\u043e\u043d\u0430 \u0437\u0430 \u0442\u0440\u0438\u0434\u0446\u0430\u0442\u044c \u043c\u0438\u043d\u0443\u0442"},"content":{"rendered":"\n
\"image\"<\/p>\n

\u041f\u043e\u0438\u0441\u043a \u043f\u0440\u043e\u0441\u0442\u044b\u0445 \u0447\u0438\u0441\u0435\u043b \u2014 \u043f\u043e\u043f\u0443\u043b\u044f\u0440\u043d\u0430\u044f \u0437\u0430\u0434\u0430\u0447\u0430 \u0441\u0440\u0435\u0434\u0438 \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0441\u0442\u043e\u0432, \u0443\u0432\u043b\u0435\u043a\u0430\u044e\u0449\u0438\u0445\u0441\u044f \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u043a\u043e\u0439. \u0421\u0430\u043c\u044b\u0439 \u0438\u0437\u0432\u0435\u0441\u0442\u043d\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c, \u043f\u0440\u0438\u0434\u0443\u043c\u0430\u043d\u043d\u044b\u0439, \u043f\u043e-\u0432\u0438\u0434\u0438\u043c\u043e\u043c\u0443, \u0431\u043e\u043b\u044c\u0448\u0435 \u0434\u0432\u0443\u0445 \u0442\u044b\u0441\u044f\u0447 \u043b\u0435\u0442 \u043d\u0430\u0437\u0430\u0434, \u2014 \u0440\u0435\u0448\u0435\u0442\u043e \u042d\u0440\u0430\u0442\u043e\u0441\u0444\u0435\u043d\u0430<\/a>; \u0432 \u043d\u0430\u0441\u0442\u043e\u044f\u0449\u0435\u0435 \u0432\u0440\u0435\u043c\u044f \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442 \u0431\u0435\u0441\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u043e\u0435 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e \u0435\u0433\u043e \u0432\u0430\u0440\u0438\u0430\u043d\u0442\u043e\u0432 \u0438 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u0439.
\u0421\u0435\u0433\u043e\u0434\u043d\u044f \u044f \u0445\u043e\u0442\u0435\u043b \u0431\u044b \u043f\u043e\u0434\u0435\u043b\u0438\u0442\u044c\u0441\u044f \u0441 \u0432\u0430\u043c\u0438 \u0440\u0430\u0437\u043b\u0438\u0447\u043d\u044b\u043c\u0438 \u0432\u0430\u0440\u0438\u0430\u043d\u0442\u0430\u043c\u0438 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438 \u043f\u043e\u0438\u0441\u043a\u0430 \u043f\u0440\u043e\u0441\u0442\u044b\u0445 \u0447\u0438\u0441\u0435\u043b \u043d\u0430 \u044f\u0437\u044b\u043a\u0435 C#, \u043d\u0430\u0447\u0438\u043d\u0430\u044f \u0441 \u043a\u043b\u0430\u0441\u0441\u0438\u0447\u0435\u0441\u043a\u0438\u0445 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u0432 \u2014 \u0440\u0435\u0448\u0435\u0442\u0430 \u042d\u0440\u0430\u0442\u043e\u0441\u0444\u0435\u043d\u0430, \u0421\u0443\u043d\u0434\u0430\u0440\u0430\u043c\u0430 \u0438 \u0410\u0442\u043a\u0438\u043d\u0430, \u0438 \u043a\u043e\u043d\u0447\u0430\u044f \u0440\u0430\u0437\u043b\u0438\u0447\u043d\u044b\u043c\u0438 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u044f\u043c\u0438 (\u0441\u0435\u0433\u043c\u0435\u043d\u0442\u0430\u0446\u0438\u044f, \u0444\u0430\u043a\u0442\u043e\u0440\u0438\u0437\u0430\u0446\u0438\u044f). \u041e\u0441\u043e\u0431\u044b\u0439 \u0443\u043f\u043e\u0440 \u044f \u0434\u0435\u043b\u0430\u043b \u043d\u0430 \u043f\u0440\u043e\u0441\u0442\u043e\u0442\u0443: \u0441\u0430\u043c\u044b\u0439 \u0431\u044b\u0441\u0442\u0440\u044b\u0439 \u0438\u0437 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u0432, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043c\u043d\u0435 \u0443\u0434\u0430\u043b\u043e\u0441\u044c \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c, \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442 120 \u0441\u0442\u0440\u043e\u043a \u043a\u043e\u0434\u0430 \u0438 \u0438\u0449\u0435\u0442 \u043f\u0440\u043e\u0441\u0442\u044b\u0435 \u0447\u0438\u0441\u043b\u0430 \u0434\u043e \u0442\u0440\u0438\u043b\u043b\u0438\u043e\u043d\u0430 \u043c\u0435\u043d\u044c\u0448\u0435, \u0447\u0435\u043c \u0437\u0430 30 \u043c\u0438\u043d\u0443\u0442, \u0430 \u0434\u043e \u043c\u0438\u043b\u043b\u0438\u0430\u0440\u0434\u0430 \u2014 \u043c\u0435\u043d\u044c\u0448\u0435, \u0447\u0435\u043c \u0437\u0430 \u0441\u0435\u043a\u0443\u043d\u0434\u0443 (\u044d\u0442\u043e \u0434\u0430\u043b\u0435\u043a\u043e \u043e\u0442 \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438 \u043b\u0443\u0447\u0448\u0438\u0445 \u0438\u0437 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u044e\u0449\u0438\u0445 \u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a \u043f\u043e \u043f\u043e\u0438\u0441\u043a\u0443 \u043f\u0440\u043e\u0441\u0442\u044b\u0445 \u0447\u0438\u0441\u0435\u043b, \u043d\u043e \u044d\u0442\u0438 \u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a\u0438 \u043e\u0431\u044b\u0447\u043d\u043e \u0441\u043e\u0434\u0435\u0440\u0436\u0430\u0442 \u0441\u0432\u044b\u0448\u0435 4000 \u0441\u0442\u0440\u043e\u043a \u043a\u043e\u0434\u0430).
\u0412 \u0437\u0430\u043a\u043b\u044e\u0447\u0435\u043d\u0438\u0435 \u043c\u044b \u043f\u0440\u0438\u043c\u0435\u043d\u0438\u043c \u0441\u0430\u043c\u0443\u044e \u0431\u044b\u0441\u0442\u0440\u0443\u044e \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044e \u0434\u043b\u044f \u043f\u043e\u0438\u0441\u043a\u0430 \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u044f \u043c\u0435\u0436\u0434\u0443 \u0434\u0432\u0443\u043c\u044f \u0441\u043e\u0441\u0435\u0434\u043d\u0438\u043c\u0438 \u043f\u0440\u043e\u0441\u0442\u044b\u043c\u0438 \u0447\u0438\u0441\u043b\u0430\u043c\u0438 \u0434\u043e \u0442\u0440\u0438\u043b\u043b\u0438\u043e\u043d\u0430. \u041f\u0440\u0435\u0436\u0434\u0435 \u0447\u0435\u043c \u0437\u0430\u0445\u043e\u0434\u0438\u0442\u044c \u043f\u043e\u0434 \u043a\u0430\u0442, \u044f \u043f\u0440\u0435\u0434\u043b\u0430\u0433\u0430\u044e \u0432\u0430\u043c \u043f\u043e\u043f\u044b\u0442\u0430\u0442\u044c\u0441\u044f \u0443\u0433\u0430\u0434\u0430\u0442\u044c \u043e\u0442\u0432\u0435\u0442. \u0414\u043b\u044f \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u044f, \u0434\u043b\u044f \u043f\u0440\u043e\u0441\u0442\u044b\u0445 \u0447\u0438\u0441\u0435\u043b \u0434\u043e 100 \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u0440\u0430\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u0440\u0430\u0432\u043d\u043e 8 (\u043c\u0435\u0436\u0434\u0443 \u0441\u043e\u0441\u0435\u0434\u043d\u0438\u043c\u0438 \u043f\u0440\u043e\u0441\u0442\u044b\u043c\u0438 \u0447\u0438\u0441\u043b\u0430\u043c\u0438 89 \u0438 97), \u0430 \u0434\u043e \u0442\u044b\u0441\u044f\u0447\u0438 \u2014 20 (\u043c\u0435\u0436\u0434\u0443 887 \u0438 907).
\u0412\u0435\u0441\u044c \u0438\u0441\u0445\u043e\u0434\u043d\u044b\u0439 \u043a\u043e\u0434 \u043c\u043e\u0436\u043d\u043e \u043d\u0430\u0439\u0442\u0438 \u043d\u0430 \u0433\u0438\u0442\u0445\u0430\u0431\u0435<\/a>.
<\/a> <\/p>\n

1. \u0420\u0435\u0448\u0435\u0442\u043e \u042d\u0440\u0430\u0442\u043e\u0441\u0444\u0435\u043d\u0430<\/h2>\n

\u0420\u0435\u0448\u0435\u0442\u043e \u042d\u0440\u0430\u0442\u043e\u0441\u0444\u0435\u043d\u0430<\/a> \u2014 \u0441\u0430\u043c\u044b\u0439 \u043f\u0440\u043e\u0441\u0442\u043e\u0439 \u0438 \u0438\u0437\u0432\u0435\u0441\u0442\u043d\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0434\u043b\u044f \u043f\u043e\u0438\u0441\u043a\u0430 \u043f\u0440\u043e\u0441\u0442\u044b\u0445 \u0447\u0438\u0441\u0435\u043b. \u0415\u0433\u043e \u0441\u0443\u0442\u044c \u0441\u043e\u0441\u0442\u043e\u0438\u0442 \u0432 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u043c:
\u2014 \u0412\u044b\u043f\u0438\u0441\u044b\u0432\u0430\u0435\u043c \u0447\u0438\u0441\u043b\u0430 2, 3, …, N;
\u2014 \u0411\u0435\u0440\u0435\u043c \u043f\u0435\u0440\u0432\u043e\u0435 \u0447\u0438\u0441\u043b\u043e \u0432 \u0441\u043f\u0438\u0441\u043a\u0435 \"$p=2$\"<\/math> \u0438 \u0432\u044b\u0447\u0435\u0440\u043a\u0438\u0432\u0430\u0435\u043c \u0438\u0437 \u0441\u043f\u0438\u0441\u043a\u0430 \u0432\u0441\u0435 \u0447\u0438\u0441\u043b\u0430, \u043a\u0440\u0430\u0442\u043d\u044b\u0435 \u0435\u043c\u0443, \u043d\u0430\u0447\u0438\u043d\u0430\u044f \u0441 \"$p^2$\"<\/math>: 4, 6, 8,\u2026
\u2014 \u0411\u0435\u0440\u0435\u043c \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u0435 \u0447\u0438\u0441\u043b\u043e \u0432 \u0441\u043f\u0438\u0441\u043a\u0435 \"$p=3$\"<\/math> \u0438 \u0432\u044b\u0447\u0435\u0440\u043a\u0438\u0432\u0430\u0435\u043c \u043a\u0440\u0430\u0442\u043d\u044b\u0435 \u0435\u043c\u0443 9, 15,\u2026
\u2014 \u041f\u0440\u043e\u0434\u043e\u043b\u0436\u0430\u0435\u043c \u043f\u0440\u043e\u0446\u0435\u0434\u0443\u0440\u0443 \u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u043f\u043e\u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u0433\u043e \u0447\u0438\u0441\u043b\u0430 \u0438\u0437 \u043e\u0441\u0442\u0430\u0432\u0448\u0438\u0445\u0441\u044f \u0432 \u0441\u043f\u0438\u0441\u043a\u0435 \"$p=5,<\/math> \u043f\u043e\u043a\u0430 \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u0442\u0441\u044f \u043d\u0435\u0440\u0430\u0432\u0435\u043d\u0441\u0442\u0432\u043e \"$p^2<\/math>; \u043e\u0441\u0442\u0430\u0432\u0448\u0438\u0435\u0441\u044f \u043f\u043e\u0441\u043b\u0435 \u044d\u0442\u043e\u0433\u043e \u0432 \u0441\u043f\u0438\u0441\u043a\u0435 \u0447\u0438\u0441\u043b\u0430 \u0438 \u0431\u0443\u0434\u0443\u0442 \u043f\u0440\u043e\u0441\u0442\u044b\u043c\u0438:
\u0432\u044b\u0447\u0435\u0440\u043a\u0438\u0432\u0430\u0435\u043c \u043a\u0440\u0430\u0442\u043d\u044b\u0435 2: [2<\/b>, 3, 4<\/s>, 5, 6<\/s>, 7, 8<\/s>, 9, 10<\/s>, 11, 12<\/s>, 13, 14<\/s>, 15, ...]
\u0432\u044b\u0447\u0435\u0440\u043a\u0438\u0432\u0430\u0435\u043c \u043a\u0440\u0430\u0442\u043d\u044b\u0435 3: [2, 3<\/b>, 5, 7, 9<\/s>, 11, 13, 15<\/s>, 17, 19, 21<\/s>, 23, 25, 27<\/s>, ...]
\u0432\u044b\u0447\u0435\u0440\u043a\u0438\u0432\u0430\u0435\u043c \u043a\u0440\u0430\u0442\u043d\u044b\u0435 5: [2, 3, 5<\/b>, 7, 11, 13, 17, 19, 23, 25<\/s>, 29, 31, 35<\/s>, ...]
\u0438 \u0442\u0430\u043a \u0434\u0430\u043b\u0435\u0435...<\/code>
\u041f\u0440\u0430\u043a\u0442\u0438\u0447\u0435\u0441\u043a\u0430\u044f \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442 \u0431\u0438\u0442\u043e\u0432\u044b\u0439 \u043c\u0430\u0441\u0441\u0438\u0432 \u0434\u043b\u0438\u043d\u044b N, \u0441 \u0432\u0441\u0435\u043c\u0438 \u0431\u0438\u0442\u0430\u043c\u0438 \u0438\u0437\u043d\u0430\u0447\u0430\u043b\u044c\u043d\u043e \u0443\u0441\u0442\u0430\u043d\u043e\u0432\u043b\u0435\u043d\u043d\u044b\u043c\u0438 \u0432 1, \u0438 \u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0441\u043e\u0441\u0442\u0430\u0432\u043d\u043e\u0433\u043e \u0447\u0438\u0441\u043b\u0430 \u043c\u0435\u043d\u044f\u0435\u0442 \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u044e\u0449\u0438\u0439 \u0431\u0438\u0442 \u043d\u0430 0. <\/p>\n

SieveOfEratosthenes.cs<\/b> <\/p>\n
\n
public class SieveOfEratosthenes : ISieve {     private BitArray Data;     public int Length => Data.Length;      public SieveOfEratosthenes(int length)     {         Data = new BitArray(length);         Data.SetAll(true);          for (int p = 2; p * p < length; p++)         {             if (Data[p])             {                 for (int i = p * p; i < Length; i += p)                 {                     Data[i] = false;                 }             }         }     }      public void ListPrimes(Action<long> callback)     {         for (int i = 2; i < Length; i++)         {             if (Data[i]) callback.Invoke(i);         }     } } <\/code><\/pre>\n
  <\/div>\n<\/p><\/div>\n
  \u041f\u043e\u0441\u043a\u043e\u043b\u044c\u043a\u0443 \u043d\u0430\u0448\u0430 \u0437\u0430\u0434\u0430\u0447\u0430 \u2014 \u0441\u0440\u0430\u0432\u043d\u0438\u0442\u044c \u043c\u0435\u0436\u0434\u0443 \u0441\u043e\u0431\u043e\u0439 \u0440\u0430\u0437\u043d\u044b\u0435 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438 \u043f\u043e\u0438\u0441\u043a\u0430 \u043f\u0440\u043e\u0441\u0442\u044b\u0445 \u0447\u0438\u0441\u0435\u043b, \u043c\u044b \u043d\u0430\u0441\u043b\u0435\u0434\u0443\u0435\u043c \u0432\u0441\u0435 \u0432\u0430\u0440\u0438\u0430\u043d\u0442\u044b \u043e\u0442 \u0438\u043d\u0442\u0435\u0440\u0444\u0435\u0439\u0441\u0430 ISieve, \u0438\u043c\u0435\u044e\u0449\u0435\u0433\u043e \u0442\u043e\u043b\u044c\u043a\u043e \u043e\u0434\u0438\u043d \u043c\u0435\u0442\u043e\u0434:  <\/p>\n
public interface ISieve {     void ListPrimes(Action<long> callback); } <\/code><\/pre>\n
  \u0414\u043b\u044f \u043f\u0435\u0440\u0435\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f \u043f\u0440\u043e\u0441\u0442\u044b\u0445 \u0447\u0438\u0441\u0435\u043b \u0431\u044b\u043b \u0432\u044b\u0431\u0440\u0430\u043d \u0441\u043f\u043e\u0441\u043e\u0431 \u043a\u043e\u043b\u0431\u0435\u043a\u043e\u0432, \u0430 \u043d\u0435 \u0431\u043e\u043b\u0435\u0435 \u043f\u0440\u0438\u0432\u044b\u0447\u043d\u044b\u0435 \u0434\u043b\u044f C# \u044d\u043d\u0443\u043c\u0435\u0440\u0430\u0442\u043e\u0440\u044b, \u043f\u043e\u0441\u043a\u043e\u043b\u044c\u043a\u0443 \u043e\u043d \u043d\u0430 10-40% \u0431\u044b\u0441\u0442\u0440\u0435\u0435. \u042d\u0442\u043e\u0442 \u0438\u043d\u0442\u0435\u0440\u0444\u0435\u0439\u0441 \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u0435\u0434\u0438\u043d\u043e\u043e\u0431\u0440\u0430\u0437\u043d\u043e \u0442\u0435\u0441\u0442\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0440\u0430\u0437\u043d\u044b\u0435 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438 \u0438 \u0441\u0440\u0430\u0432\u043d\u0438\u0432\u0430\u0442\u044c \u0438\u0445 \u043c\u0435\u0436\u0434\u0443 \u0441\u043e\u0431\u043e\u0439; \u0432 \u0447\u0430\u0441\u0442\u043d\u043e\u0441\u0442\u0438, \u043c\u044b \u0431\u0443\u0434\u0435\u043c \u0441\u0447\u0438\u0442\u0430\u0442\u044c \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e, \u0441\u0443\u043c\u043c\u0443 \u0438 \u0445\u0435\u0448 \u043f\u0440\u043e\u0441\u0442\u044b\u0445 \u0447\u0438\u0441\u0435\u043b \u0434\u043e \u043c\u0438\u043b\u043b\u0438\u0430\u0440\u0434\u0430:  <\/p>\n
                         PerformanceTests<\/b>                         <\/p>\n
\n
static void TestSieve<T>(long length,                           long expectedCount,                          long expectedSum,                          long expectedHash) {     var sw = Stopwatch.StartNew();     ISieve sieve = CreateSieve<T>(length);     long count = 0, sum = 0, hash = 0;     Action<long> action = (p) => { count++; sum += p; hash = hash * 31 + p; };     sieve.ListPrimes(action);     AssertEquals(expectedCount, count);     AssertEquals(expectedSum, sum);     AssertEquals(expectedHash, hash);     Console.WriteLine($"{typeof(T).Name} up to {length:N0} in {sw.Elapsed}"); }  static void TestSieve_1G<T>() =>     TestSieve<T>(1_000_000_000, 50847534, 24739512092254535, 1480810120364005255); <\/code><\/pre>\n
  <\/div>\n<\/p><\/div>\n
  \u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c: \u0440\u0435\u0448\u0435\u0442\u043e \u042d\u0440\u0430\u0442\u043e\u0441\u0444\u0435\u043d\u0430<\/b>
  \u0418\u0449\u0435\u0442 \u043f\u0440\u043e\u0441\u0442\u044b\u0435 \u0447\u0438\u0441\u043b\u0430 \u0434\u043e \u043c\u0438\u043b\u043b\u0438\u0430\u0440\u0434\u0430: 12.6 \u0441\u0435\u043a\u0443\u043d\u0434<\/b>.<\/p>\n
2. \u0420\u0435\u0448\u0435\u0442\u043e \u0421\u0443\u043d\u0434\u0430\u0440\u0430\u043c\u0430<\/h2>\n
  \u0420\u0435\u0448\u0435\u0442\u043e \u0421\u0443\u043d\u0434\u0430\u0440\u0430\u043c\u0430<\/a> \u2014 \u0432\u0442\u043e\u0440\u043e\u0439 \u043f\u043e \u0438\u0437\u0432\u0435\u0441\u0442\u043d\u043e\u0441\u0442\u0438 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043f\u043e\u0438\u0441\u043a\u0430 \u043d\u0435\u0447\u0435\u0442\u043d\u044b\u0445 \u043f\u0440\u043e\u0441\u0442\u044b\u0445 \u0447\u0438\u0441\u0435\u043b, \u043f\u0440\u0438\u0434\u0443\u043c\u0430\u043d\u043d\u044b\u0439 \u0438\u043d\u0434\u0438\u0439\u0441\u043a\u0438\u043c \u0441\u0442\u0443\u0434\u0435\u043d\u0442\u043e\u043c \u0421\u0443\u043d\u0434\u0430\u0440\u0430\u043c\u043e\u043c \u0432 1934 \u0433\u043e\u0434\u0443. \u0415\u0433\u043e \u0441\u0443\u0442\u044c \u0441\u043e\u0441\u0442\u043e\u0438\u0442 \u0432 \u0432\u044b\u0447\u0435\u0440\u043a\u0438\u0432\u0430\u043d\u0438\u0438 \u0438\u0437 \u0441\u043f\u0438\u0441\u043a\u0430 \u0447\u0438\u0441\u0435\u043b \u043e\u0442 1 \u0434\u043e \"$(N-1)\/2$\"<\/math> \u0432\u0441\u0435\u0445 \u0447\u0438\u0441\u0435\u043b \u0432\u0438\u0434\u0430 <\/p>\n
\"$i+j+2ij$\"<\/math><\/p>\n<\/p>\n
\"$1<=i<=j$\"<\/math><\/p>\n
 \u041f\u043e\u0441\u043b\u0435 \u044d\u0442\u043e\u0433\u043e, \u0434\u043b\u044f \u043e\u0441\u0442\u0430\u0432\u0448\u0438\u0445\u0441\u044f \u0432 \u0441\u043f\u0438\u0441\u043a\u0435 \u0447\u0438\u0441\u0435\u043b \"$n_i$\"<\/math>, \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c \u0447\u0438\u0441\u0435\u043b \"$2n_i+1$\"<\/math> \u0431\u0443\u0434\u0435\u0442 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u044f\u0442\u044c \u0432\u0441\u0435 \u043d\u0435\u0447\u0435\u0442\u043d\u044b\u0435 \u043f\u0440\u043e\u0441\u0442\u044b\u0435 \u0447\u0438\u0441\u043b\u0430 \u0434\u043e N.
  \u0432\u044b\u0447\u0435\u0440\u043a\u0438\u0432\u0430\u0435\u043c 1+j+2*1*j: [1, 2, 3, 4<\/s>, 5, 6, 7<\/s>, 8, 9, 10<\/s>, ...]
  \u0432\u044b\u0447\u0435\u0440\u043a\u0438\u0432\u0430\u0435\u043c 2+j+2*2*j: [1, 2, 3, 5, 6, 8, 9, 11, 12<\/s>, 14, 15, ...]
  \u0432\u044b\u0447\u0435\u0440\u043a\u0438\u0432\u0430\u0435\u043c 3+j+2*3*j: [1, 2, 3, 5, 6, 8, 9, 10, 11, 14, ..., 24<\/s>, ...]
  \u0438 \u0442\u0430\u043a \u0434\u0430\u043b\u0435\u0435...
  \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c 2n+1: [3, 5, 7, 11, 13, 17, 19, ...]<\/code>  <\/p>\n
                         SieveOfSundaram.cs<\/b>                         <\/p>\n
\n
public class SieveOfSundaram : ISieve {     private BitArray Data;     public int Length { get; private set; }      public SieveOfSundaram(int length)     {         Length = length;         Data = new BitArray((Length + 1) \/ 2);         Data.SetAll(true);          for (int i = 1; i + i + 2 * i * i < Data.Length; i++)         {             for (int j = i; i + j + 2 * i * j < Data.Length; j++)             {                 Data[i + j + 2 * i * j] = false;             }         }     }      public void ListPrimes(Action<long> callback)     {         callback.Invoke(2);          for (int i = 1; i < Data.Length; i++)         {             if (Data[i])             {                 int p = i * 2 + 1;                 if (p >= Length) break;                 callback.Invoke(p);             }         }     } } <\/code><\/pre>\n
  <\/div>\n<\/p><\/div>\n
   \u0417\u0430\u043c\u0435\u0442\u0438\u043c, \u0447\u0442\u043e, \u0432 \u043e\u0442\u043b\u0438\u0447\u0438\u0435 \u043e\u0442 \u0440\u0435\u0448\u0435\u0442\u0430 \u042d\u0440\u0430\u0442\u043e\u0441\u0444\u0435\u043d\u0430, \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0432\u044b\u0447\u0435\u0440\u043a\u0438\u0432\u0430\u0435\u0442 \u0447\u0438\u0441\u043b\u0430 \u0434\u043b\u044f \u043b\u044e\u0431\u044b\u0445 \u043a\u043e\u043c\u0431\u0438\u043d\u0430\u0446\u0438\u0439 \"$(i,<\/math>, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u0435\u0433\u043e \u0442\u0435\u043e\u0440\u0435\u0442\u0438\u0447\u0435\u0441\u043a\u0430\u044f \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u0445\u0443\u0436\u0435: \"$O(N<\/math> \u043f\u0440\u043e\u0442\u0438\u0432 \"$O(N<\/math>. \u0418 \u0434\u0435\u0439\u0441\u0442\u0432\u0438\u0442\u0435\u043b\u044c\u043d\u043e, \u043d\u0430 \u043d\u0430\u0448\u0435\u043c \u0442\u0435\u0441\u0442\u0435 \u043e\u043d \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u043c\u0435\u0434\u043b\u0435\u043d\u043d\u0435\u0439:<\/p>\n
  \u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c: \u0440\u0435\u0448\u0435\u0442\u043e \u0421\u0443\u043d\u0434\u0430\u0440\u0430\u043c\u0430<\/b>
  \u0418\u0449\u0435\u0442 \u043f\u0440\u043e\u0441\u0442\u044b\u0435 \u0447\u0438\u0441\u043b\u0430 \u0434\u043e \u043c\u0438\u043b\u043b\u0438\u0430\u0440\u0434\u0430: 18 \u0441\u0435\u043a\u0443\u043d\u0434<\/b>.<\/p>\n
3. \u0420\u0435\u0448\u0435\u0442\u043e \u0410\u0442\u043a\u0438\u043d\u0430<\/h2>\n
  \u0412 2003 \u0433\u043e\u0434\u0443 \u0434\u0432\u0430 \u043f\u0440\u043e\u0444\u0435\u0441\u0441\u043e\u0440\u0430 \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u043a\u0438 \u0438\u0437 \u0418\u043b\u043b\u0438\u043d\u043e\u0439\u0441\u043a\u043e\u0433\u043e \u0443\u043d\u0438\u0432\u0435\u0440\u0441\u0438\u0442\u0435\u0442\u0430 \u0432 \u0427\u0438\u043a\u0430\u0433\u043e \u0410\u0440\u0442\u0443\u0440 \u0410\u0442\u043a\u0438\u043d \u0438 \u0414\u0430\u043d\u0438\u044d\u043b\u044c \u0411\u0435\u0440\u043d\u0448\u0442\u0435\u0439\u043d \u043e\u043f\u0443\u0431\u043b\u0438\u043a\u043e\u0432\u0430\u043b\u0438 \u0441\u0442\u0430\u0442\u044c\u044e, \u043e\u043f\u0438\u0441\u044b\u0432\u0430\u044e\u0449\u0443\u044e \u043f\u0440\u0438\u043d\u0446\u0438\u043f\u0438\u0430\u043b\u044c\u043d\u043e \u043d\u043e\u0432\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043f\u043e\u0438\u0441\u043a\u0430 \u043f\u0440\u043e\u0441\u0442\u044b\u0445 \u0447\u0438\u0441\u0435\u043b, \u043e\u043f\u0438\u0440\u0430\u044e\u0449\u0438\u0439\u0441\u044f \u043d\u0430 \u043c\u0435\u0442\u043e\u0434\u044b \u0430\u043b\u0433\u0435\u0431\u0440\u0430\u0438\u0447\u0435\u0441\u043a\u043e\u0439 \u0442\u0435\u043e\u0440\u0438\u0438 \u0447\u0438\u0441\u0435\u043b. \u042d\u0442\u043e\u0442 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0442\u0435\u043f\u0435\u0440\u044c \u0438\u0437\u0432\u0435\u0441\u0442\u0435\u043d \u043a\u0430\u043a \u0440\u0435\u0448\u0435\u0442\u043e \u0410\u0442\u043a\u0438\u043d\u0430<\/a>. \u0415\u0433\u043e \u043e\u0441\u043d\u043e\u0432\u043d\u0430\u044f \u0438\u0434\u0435\u044f \u0441\u043e\u0441\u0442\u043e\u0438\u0442 \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u044e\u0442 \u043a\u0432\u0430\u0434\u0440\u0430\u0442\u0438\u0447\u043d\u044b\u0435 \u0444\u043e\u0440\u043c\u044b \"$ax^2<\/math> \u0434\u043b\u044f \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u043d\u044b\u0445 \u043a\u043b\u0430\u0441\u0441\u043e\u0432 \"$n$\"<\/math>, \u0438\u043c\u0435\u044e\u0449\u0438\u0435 \u043d\u0435\u0447\u0435\u0442\u043d\u043e\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0440\u0435\u0448\u0435\u043d\u0438\u0439 \u0442\u043e\u043b\u044c\u043a\u043e \u043a\u043e\u0433\u0434\u0430 \"$n$\"<\/math> \u2014 \u043b\u0438\u0431\u043e \u043f\u0440\u043e\u0441\u0442\u043e\u0435, \u043b\u0438\u0431\u043e \u0438\u043c\u0435\u0435\u0442 \u0434\u0435\u043b\u0438\u0442\u0435\u043b\u044c \"$p^2$\"<\/math>. \u042d\u0442\u043e \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u043a\u0432\u0430\u0434\u0440\u0430\u0442\u0438\u0447\u043d\u044b\u0445 \u0444\u043e\u0440\u043c \u043e\u0442\u0441\u0435\u0438\u0442\u044c \u0432\u0441\u0435 \u0441\u043e\u0441\u0442\u0430\u0432\u043d\u044b\u0435 \u0447\u0438\u0441\u043b\u0430, \u043d\u0435 \u0434\u0435\u043b\u044f\u0449\u0438\u0435\u0441\u044f \u043d\u0430 \u043a\u0432\u0430\u0434\u0440\u0430\u0442 \u043f\u0440\u043e\u0441\u0442\u043e\u0433\u043e \u0447\u0438\u0441\u043b\u0430, \u0430 \u043f\u043e\u0442\u043e\u043c \u0441\u043f\u043e\u0441\u043e\u0431\u043e\u043c, \u0430\u043d\u0430\u043b\u043e\u0433\u0438\u0447\u043d\u044b\u043c \u0440\u0435\u0448\u0435\u0442\u0443 \u042d\u0440\u0430\u0442\u043e\u0441\u0444\u0435\u043d\u0430, \u043e\u0442\u0441\u0435\u0438\u0442\u044c \u043a\u0440\u0430\u0442\u043d\u044b\u0435 \u043a\u0432\u0430\u0434\u0440\u0430\u0442\u0430\u043c \u043f\u0440\u043e\u0441\u0442\u044b\u0445 \u0447\u0438\u0441\u0435\u043b. 
  \u041f\u0435\u0440\u0432\u044b\u0439 \u0448\u0430\u0433 \u0438\u043c\u0435\u0435\u0442 \u0438\u0437\u044f\u0449\u043d\u0443\u044e \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044e \u043d\u0430 \u0431\u0438\u0442\u043e\u0432\u044b\u0445 \u043c\u0430\u0441\u0441\u0438\u0432\u0430\u0445: \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u043a\u0432\u0430\u0434\u0440\u0430\u0442\u0438\u0447\u043d\u043e\u0439 \u0444\u043e\u0440\u043c\u044b \u0432\u044b\u0447\u0438\u0441\u043b\u044f\u0435\u0442\u0441\u044f \u0434\u043b\u044f \u0432\u0441\u0435\u0445 \u043f\u043e\u0434\u0445\u043e\u0434\u044f\u0449\u0438\u0445 \u043a\u043e\u043c\u0431\u0438\u043d\u0430\u0446\u0438\u0439 \"$(x,<\/math>, \u0438 \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u044e\u0449\u0438\u0439 \u0431\u0438\u0442 \u043c\u0435\u043d\u044f\u0435\u0442\u0441\u044f \u043d\u0430 \u043f\u0440\u043e\u0442\u0438\u0432\u043e\u043f\u043e\u043b\u043e\u0436\u043d\u044b\u0439<\/b>. \u0422\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c, \u0435\u0441\u043b\u0438 \u0438\u0437\u043d\u0430\u0447\u0430\u043b\u044c\u043d\u043e \u0432\u0441\u0435 \u0431\u0438\u0442\u044b \u0431\u044b\u043b\u0438 \u0443\u0441\u0442\u0430\u043d\u043e\u0432\u043b\u0435\u043d\u044b \u0432 0, \u0442\u043e \u0432 \u043a\u043e\u043d\u0446\u0435 \u0431\u0443\u0434\u0443\u0442 \u0435\u0434\u0438\u043d\u0438\u0447\u043d\u044b\u043c\u0438 \u0442\u043e\u043b\u044c\u043a\u043e \u0431\u0438\u0442\u044b, \u043f\u0435\u0440\u0435\u043a\u043b\u044e\u0447\u0435\u043d\u043d\u044b\u0435 \u043d\u0435\u0447\u0435\u0442\u043d\u043e\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0440\u0430\u0437, \u0442\u043e \u0435\u0441\u0442\u044c \u0431\u0438\u0442\u044b \u0434\u043b\u044f \u0442\u0435\u0445 \u0447\u0438\u0441\u0435\u043b \"$n$\"<\/math>, \u0434\u043b\u044f \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u044e\u0449\u0430\u044f \u043a\u0432\u0430\u0434\u0440\u0430\u0442\u0438\u0447\u043d\u0430\u044f \u0444\u043e\u0440\u043c\u0430 \u0438\u043c\u0435\u0435\u0442 \u043d\u0435\u0447\u0435\u0442\u043d\u043e\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0440\u0435\u0448\u0435\u043d\u0438\u0439!
  \u041f\u0440\u0430\u043a\u0442\u0438\u0447\u0435\u0441\u043a\u0430\u044f \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u0435\u0442 \u0447\u0438\u0441\u043b\u0430 \"$n$\"<\/math>, \u043d\u0435 \u0434\u0435\u043b\u044f\u0449\u0438\u0435\u0441\u044f \u043d\u0430 2, 3, 5, \u0438 \u0438\u043c\u0435\u044e\u0449\u0438\u0435 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u043d\u044b\u0435 \u043e\u0441\u0442\u0430\u0442\u043a\u0438 \u043e\u0442 \u0434\u0435\u043b\u0435\u043d\u0438\u044f \u043d\u0430 60.  <\/p>\n
                         SieveOfAtkin.cs<\/b>                         <\/p>\n
\n
public class SieveOfAtkin : ISieve {     private BitArray Data;     public int Length { get; private set; }      public SieveOfAtkin(int length)     {         Length = length;         Data = new BitArray(Length);         Data.SetAll(false);          SieveQuadForm1(Data);         SieveQuadForm2(Data);         SieveQuadForm3(Data);          for (int p = 7; p * p <= length; p++)         {             if (Data[p])             {                 for (int i = p * p; i < Length; i += p * p)                 {                     Data[i] = false;                 }             }         }      }      private void SieveQuadForm1(BitArray data)     {         for (int x = 1; 4 * x * x < data.Length; x++)         {             for (int y = 1; 4 * x * x + y * y < data.Length; y += 2)             {                 int n = 4 * x * x + y * y;                 int rem = n % 60;                 if (rem == 1 || rem == 13 || rem == 17 || rem == 29 ||                      rem == 37 || rem == 41 || rem == 49 || rem == 53)                 {                     data[n] = !data[n];                 }             }         }     }      private void SieveQuadForm2(BitArray data)     {         for (int x = 1; 3 * x * x < data.Length; x += 2)         {             for (int y = 2; 3 * x * x + y * y < data.Length; y += 2)             {                 int n = 3 * x * x + y * y;                 int rem = n % 60;                 if (rem == 7 || rem == 19 || rem == 31 || rem == 43)                 {                     data[n] = !data[n];                 }             }         }     }      private void SieveQuadForm3(BitArray data)     {         for (int x = 1; 2 * x * x < data.Length; x++)         {             for (int y = x - 1; y > 0; y -= 2)             {                 int n = 3 * x * x - y * y;                 if (n >= data.Length) continue;                 int rem = n % 60;                 if (rem == 11 || rem == 23 || rem == 47 || rem == 59)                 {                     data[n] = !data[n];                 }             }         }     }      public void ListPrimes(Action<long> callback)     {         callback.Invoke(2);         callback.Invoke(3);         callback.Invoke(5);         for (int i = 7; i < Length; i++)         {             if (Data[i])             {                 callback.Invoke(i);             }         }     } } <\/code><\/pre>\n
  <\/div>\n<\/p><\/div>\n
  \u042d\u0442\u043e\u0442 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0430\u0441\u0438\u043c\u043f\u0442\u043e\u0442\u0438\u0447\u0435\u0441\u043a\u0438 \u0431\u044b\u0441\u0442\u0440\u0435\u0435, \u0447\u0435\u043c \u0440\u0435\u0448\u0435\u0442\u043e \u042d\u0440\u0430\u0442\u043e\u0441\u0444\u0435\u043d\u0430: \"$O(N)$\"<\/math> \u043f\u0440\u043e\u0442\u0438\u0432 \"$O(N<\/math>, \u043d\u043e \u0437\u0430 \u0441\u0447\u0435\u0442 \u0431\u043e\u043b\u044c\u0448\u0435\u0439 \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u0438 \u0432 \u043f\u0440\u0430\u043a\u0442\u0438\u0447\u0435\u0441\u043a\u043e\u043c \u043f\u0440\u0438\u043c\u0435\u043d\u0435\u043d\u0438\u0438 \u0447\u0430\u0441\u0442\u043e \u043f\u0440\u043e\u0438\u0433\u0440\u044b\u0432\u0430\u0435\u0442 \u0440\u0435\u0448\u0435\u0442\u0443 \u042d\u0440\u0430\u0442\u043e\u0441\u0444\u0435\u043d\u0430 \u043f\u0440\u0438 \u0441\u0440\u0430\u0432\u043d\u0438\u043c\u043e\u043c \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0435 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u0439.<\/p>\n
  \u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c: \u0440\u0435\u0448\u0435\u0442\u043e \u0410\u0442\u043a\u0438\u043d\u0430<\/b>
  \u0418\u0449\u0435\u0442 \u043f\u0440\u043e\u0441\u0442\u044b\u0435 \u0447\u0438\u0441\u043b\u0430 \u0434\u043e \u043c\u0438\u043b\u043b\u0438\u0430\u0440\u0434\u0430: 11.4 \u0441\u0435\u043a\u0443\u043d\u0434<\/b>.<\/p>\n
4. \u041a\u043e\u043b\u0451\u0441\u043d\u0430\u044f \u0444\u0430\u043a\u0442\u043e\u0440\u0438\u0437\u0430\u0446\u0438\u044f<\/h2>\n
  \u041a\u043e\u043b\u0451\u0441\u043d\u0430\u044f \u0444\u0430\u043a\u0442\u043e\u0440\u0438\u0437\u0430\u0446\u0438\u044f<\/a> \u2014 \u0432\u0438\u0434 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u0438 \u0440\u0435\u0448\u0435\u0442\u0430 \u042d\u0440\u0430\u0442\u043e\u0441\u0444\u0435\u043d\u0430, \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u044e\u0449\u0438\u0439 \u0437\u0430\u0440\u0430\u043d\u0435\u0435 \u0438\u0441\u043a\u043b\u044e\u0447\u0438\u0442\u044c \u0438\u0437 \u0440\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0435\u043d\u0438\u044f \u0447\u0438\u0441\u043b\u0430, \u0437\u0430\u0432\u0435\u0434\u043e\u043c\u043e \u043d\u0435 \u044f\u0432\u043b\u044f\u044e\u0449\u0438\u0435\u0441\u044f \u043f\u0440\u043e\u0441\u0442\u044b\u043c\u0438. \u041d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u043b\u044e\u0431\u043e\u0435 \u043f\u0440\u043e\u0441\u0442\u043e\u0435 \u0447\u0438\u0441\u043b\u043e, \u0431\u043e\u043b\u044c\u0448\u0435\u0435 6, \u0438\u043c\u0435\u0435\u0442 \u043e\u0441\u0442\u0430\u0442\u043e\u043a \u043e\u0442 \u0434\u0435\u043b\u0435\u043d\u0438\u044f \u043d\u0430 6 \u043b\u0438\u0431\u043e 1, \u043b\u0438\u0431\u043e 5: \"$p<\/math> \u0438\u043b\u0438 \"$p=6k+5$\"<\/math>: \u043f\u0440\u0438 \u043b\u044e\u0431\u044b\u0445 \u0434\u0440\u0443\u0433\u0438\u0445 \u043e\u0441\u0442\u0430\u0442\u043a\u0430\u0445 \u0447\u0438\u0441\u043b\u043e \u0431\u0443\u0434\u0435\u0442 \u0434\u0435\u043b\u0438\u0442\u044c\u0441\u044f \u043b\u0438\u0431\u043e \u043d\u0430 2, \u043b\u0438\u0431\u043e \u043d\u0430 3. \u0410\u043d\u0430\u043b\u043e\u0433\u0438\u0447\u043d\u043e, \u043f\u0440\u043e\u0441\u0442\u043e\u0435 \u0447\u0438\u0441\u043b\u043e, \u0431\u043e\u043b\u044c\u0448\u0435\u0435 \"$2*3*5=30$\"<\/math>, \u043c\u043e\u0436\u0435\u0442 \u0438\u043c\u0435\u0442\u044c \u0442\u043e\u043b\u044c\u043a\u043e \u043e\u0434\u0438\u043d \u0438\u0437 8 \u043e\u0441\u0442\u0430\u0442\u043a\u043e\u0432 \u043e\u0442 \u0434\u0435\u043b\u0435\u043d\u0438\u044f \u043d\u0430 30: \"$(1,<\/math>. \u0415\u0449\u0435 \u043e\u0434\u043d\u043e \u043f\u0440\u0435\u0438\u043c\u0443\u0449\u0435\u0441\u0442\u0432\u043e \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u0438 \u2014 \u0443\u043c\u0435\u043d\u044c\u0448\u0435\u043d\u0438\u0435 \u043f\u043e\u0442\u0440\u0435\u0431\u0435\u043d\u0438\u044f \u043f\u0430\u043c\u044f\u0442\u0438: \u0432\u043c\u0435\u0441\u0442\u043e \u043e\u0434\u043d\u043e\u0433\u043e \u0431\u0438\u0442\u0430 \u043d\u0430 \u0447\u0438\u0441\u043b\u043e \u0434\u043b\u044f \u0440\u0435\u0448\u0435\u0442\u0430 \u042d\u0440\u0430\u0442\u043e\u0441\u0444\u0435\u043d\u0430 \u0438\u043b\u0438 0.5 \u0431\u0438\u0442 \u043d\u0430 \u0447\u0438\u0441\u043b\u043e \u0434\u043b\u044f \u0440\u0435\u0448\u0435\u0442\u0430 \u0421\u0443\u043d\u0434\u0430\u0440\u0430\u043c\u0430, \u0444\u0430\u043a\u0442\u043e\u0440\u0438\u0437\u0430\u0446\u0438\u044f \u0441 \u0431\u0430\u0437\u043e\u0439 \"$(2,<\/math> \u0442\u0440\u0435\u0431\u0443\u0435\u0442 \u043f\u0440\u0438\u043c\u0435\u0440\u043d\u043e 0.27 \u0431\u0438\u0442 \u043d\u0430 \u0447\u0438\u0441\u043b\u043e, \u043f\u043e\u0441\u043a\u043e\u043b\u044c\u043a\u0443 \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u0445\u0440\u0430\u043d\u0438\u0442\u044c 30 \u0447\u0438\u0441\u0435\u043b \u0432 8 \u0431\u0438\u0442\u0430\u0445. \u041f\u0440\u0438 \u0430\u043a\u043a\u0443\u0440\u0430\u0442\u043d\u043e\u043c \u043f\u0440\u0438\u043c\u0435\u043d\u0435\u043d\u0438\u0438 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u044f \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u0443\u0441\u043a\u043e\u0440\u0438\u0442\u044c \u043f\u0440\u043e\u0441\u0435\u0438\u0432\u0430\u043d\u0438\u0435 \u0432 \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0440\u0430\u0437, \u043e\u0434\u043d\u0430\u043a\u043e \u043d\u0435\u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0435 \u0432\u0430\u0440\u0438\u0430\u043d\u0442\u044b \u043e\u0431\u044b\u0447\u043d\u043e \u0440\u0430\u0431\u043e\u0442\u0430\u044e\u0442 \u043c\u0435\u0434\u043b\u0435\u043d\u043d\u043e \u0437\u0430 \u0441\u0447\u0435\u0442 \u0431\u043e\u043b\u044c\u0448\u0435\u0439 \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u0438. \u0412 \u043f\u0440\u043e\u0448\u043b\u043e\u0439 \u043f\u0443\u0431\u043b\u0438\u043a\u0430\u0446\u0438\u0438<\/a> \u044f \u043f\u043e\u0434\u0440\u043e\u0431\u043d\u043e \u043e\u043f\u0438\u0441\u044b\u0432\u0430\u043b \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c, \u043e\u0434\u043d\u0430\u043a\u043e \u043e\u043d \u043d\u0435 \u0431\u044b\u043b \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u043d \u043f\u043e \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u0437\u0434\u0435\u0441\u044c \u044f \u043f\u0440\u0438\u0432\u0435\u0434\u0443 \u0431\u043e\u043b\u0435\u0435 \u043f\u0440\u043e\u0441\u0442\u043e\u0439 \u0438 \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u044b\u0439 \u0432\u0430\u0440\u0438\u0430\u043d\u0442.  <\/p>\n
                         Wheel235.cs<\/b>                         <\/p>\n
\n
public class Wheel235 : ISieve {     private static int[] BIT_TO_INDEX = new int[] { 1, 7, 11, 13, 17, 19, 23, 29 };      private static int[] INDEX_TO_BIT = new int[] {             -1, 0,             -1, -1, -1, -1, -1, 1,             -1, -1, -1, 2,             -1, 3,             -1, -1, -1, 4,             -1, 5,             -1, -1, -1, 6,             -1, -1, -1, -1, -1, 7,         };      private byte[] Data;     public long Length { get; private set; }      public Wheel235(long length)     {         Length = length;         Data = new byte[(length + 29) \/ 30];         for (long i = 0; i < Data.Length; i++) Data[i] = byte.MaxValue;          for (long i = 7; i * i < Length; i++)         {             if (!IsPrime(i)) continue;             for (long d = i * i; d < Length; d += i) ClearPrime(d);         }     }      public bool IsPrime(long n)     {         if (n >= Length) throw new ArgumentException("Number too big");         if (n <= 5) return n == 2 || n == 3 || n == 5;         int bit = INDEX_TO_BIT[n % 30];         if (bit < 0) return false;         return (Data[n \/ 30] & (1 << bit)) != 0;     }      private void ClearPrime(long n)     {         int bit = INDEX_TO_BIT[n % 30];         if (bit < 0) return;         Data[n \/ 30] &= (byte)~(1 << bit);     }      public void ListPrimes(Action<long> callback)     {         callback.Invoke(2);         callback.Invoke(3);         callback.Invoke(5);          for (long position = 0; position < Data.Length; position++)         {             for (int bit = 0; bit < 8; bit++)             {                 if ((Data[position] & (1 << bit)) != 0)                 {                     long p = position * 30 + BIT_TO_INDEX[bit];                     if (p <= 5) continue;                     if (p >= Length) return;                     callback.Invoke(p);                 }             }         }     } } <\/code><\/pre>\n
  <\/div>\n<\/p><\/div>\n
  \u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c: (2,3,5)-\u0444\u0430\u043a\u0442\u043e\u0440\u0438\u0437\u0430\u0446\u0438\u044f<\/b>
  \u0418\u0449\u0435\u0442 \u043f\u0440\u043e\u0441\u0442\u044b\u0435 \u0447\u0438\u0441\u043b\u0430 \u0434\u043e \u043c\u0438\u043b\u043b\u0438\u0430\u0440\u0434\u0430: 9.6 \u0441\u0435\u043a\u0443\u043d\u0434<\/b>.<\/p>\n
5. \u041e\u043f\u0442\u0438\u043c\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0435 \u0440\u0435\u0448\u0435\u0442\u043e \u042d\u0440\u0430\u0442\u043e\u0441\u0444\u0435\u043d\u0430<\/h2>\n
  \u0412 \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b\u044c\u043d\u043e\u043c \u0440\u0435\u0448\u0435\u0442\u0435 \u042d\u0440\u0430\u0442\u043e\u0441\u0444\u0435\u043d\u0430 \u043c\u044b \u0441\u043e\u0437\u0434\u0430\u0432\u0430\u043b\u0438 \u0431\u0438\u0442\u043e\u0432\u044b\u0439 \u043c\u0430\u0441\u0441\u0438\u0432 \u0434\u043b\u044f \u0432\u0441\u0435\u0445 \u0447\u0438\u0441\u0435\u043b, \u0445\u043e\u0442\u044f \u043e\u0447\u0435\u0432\u0438\u0434\u043d\u043e, \u0447\u0442\u043e \u043f\u0440\u043e\u0441\u0442\u044b\u0435 \u0447\u0438\u0441\u043b\u0430, \u043a\u0440\u043e\u043c\u0435 \u0434\u0432\u043e\u0439\u043a\u0438, \u043d\u0435 \u043c\u043e\u0433\u0443\u0442 \u0431\u044b\u0442\u044c \u0447\u0435\u0442\u043d\u044b\u043c\u0438. \u041f\u043e\u044d\u0442\u043e\u043c\u0443 \u043c\u044b \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0438\u0440\u0443\u0435\u043c \u0445\u0440\u0430\u043d\u0435\u043d\u0438\u0435, \u0441\u043e\u0437\u0434\u0430\u0432\u0430\u044f \u043c\u0430\u0441\u0441\u0438\u0432, \u0432 \u043a\u043e\u0442\u043e\u0440\u043e\u043c \u043a\u0430\u0436\u0434\u044b\u0439 \u0431\u0438\u0442 \u0431\u0443\u0434\u0435\u0442 \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u043e\u0432\u0430\u0442\u044c \u043d\u0435\u0447\u0435\u0442\u043d\u044b\u043c \u0447\u0438\u0441\u043b\u0430\u043c. \u0421\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0435\u043d\u043d\u043e, \u043d\u0435\u0447\u0435\u0442\u043d\u043e\u0435 \u0447\u0438\u0441\u043b\u043e \"$n$\"<\/math> \u0431\u0443\u0434\u0435\u0442 \u0445\u0440\u0430\u043d\u0438\u0442\u044c\u0441\u044f \u0432 \u0431\u0438\u0442\u0435 \u0441 \u043d\u043e\u043c\u0435\u0440\u043e\u043c \"$(n<\/math>. \u041a\u0440\u043e\u043c\u0435 \u0442\u043e\u0433\u043e, \u043f\u0440\u0438 \u043f\u0440\u043e\u0441\u0435\u0438\u0432\u0430\u043d\u0438\u0438 \u0447\u0438\u0441\u0435\u043b, \u043a\u0440\u0430\u0442\u043d\u044b\u0445 \u043d\u0435\u0447\u0435\u0442\u043d\u044b\u043c \u043f\u0440\u043e\u0441\u0442\u044b\u043c \"$p$\"<\/math>, \u043c\u044b \u043c\u043e\u0436\u0435\u043c \u043f\u0440\u043e\u043f\u0443\u0441\u043a\u0430\u0442\u044c \u0447\u0435\u0442\u043d\u044b\u0435 \u0447\u0438\u0441\u043b\u0430 \"$p^2<\/math> \u0438 \u043e\u0431\u0440\u0430\u0431\u0430\u0442\u044b\u0432\u0430\u0442\u044c \u0442\u043e\u043b\u044c\u043a\u043e \u043d\u0435\u0447\u0435\u0442\u043d\u044b\u0435 \u0447\u0438\u0441\u043b\u0430 \"$p^2<\/math>  <\/p>\n
                         OptimizedSieveOfEratosthenes.cs<\/b>                         <\/p>\n
\n
public class OptimizedSieveOfEratosthenes : ISieve {     private BitArray Data;     public int Length { get; private set; }      public OptimizedSieveOfEratosthenes(int length)     {         Length = length;         Data = new BitArray(Length \/ 2 + 1);         Data.SetAll(true);          int maxFactor = (int)Math.Sqrt(Length);          for (int p = 3; p <= maxFactor; p += 2)         {             if (Data[p \/ 2])             {                 for (int i = p * p; i < Length; i += 2 * p)                 {                     Data[i \/ 2] = false;                 }             }         }     }      public void ListPrimes(Action<long> callback)     {         callback.Invoke(2);          for (int i = 1; i < Length \/ 2; i++)         {             if (Data[i])             {                 long p = i * 2 + 1;                 if (p >= Length) break;                 callback.Invoke(p);             }         }     } } <\/code><\/pre>\n
  <\/div>\n<\/p><\/div>\n
  \u042d\u0442\u0430 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u044f \u0434\u0430\u0435\u0442 \u043d\u0430\u043c \u043f\u0440\u0430\u043a\u0442\u0438\u0447\u0435\u0441\u043a\u0438 \u0434\u0432\u0443\u043a\u0440\u0430\u0442\u043d\u044b\u0439 \u0432\u044b\u0438\u0433\u0440\u044b\u0448 \u0432 \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438, \u0438, \u043a\u0440\u043e\u043c\u0435 \u0442\u043e\u0433\u043e, \u0442\u0440\u0435\u0431\u0443\u0435\u0442 0.5 \u0431\u0438\u0442\u0430 \u043d\u0430 \u043d\u0430\u0442\u0443\u0440\u0430\u043b\u044c\u043d\u043e\u0435 \u0447\u0438\u0441\u043b\u043e, \u043a\u0430\u043a \u0438 \u0440\u0435\u0448\u0435\u0442\u043e \u0421\u0443\u043d\u0434\u0430\u0440\u0430\u043c\u0430.<\/p>\n
  \u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c: \u041e\u043f\u0442\u0438\u043c\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0435 \u0440\u0435\u0448\u0435\u0442\u043e \u042d\u0440\u0430\u0442\u043e\u0441\u0444\u0435\u043d\u0430<\/b>
  \u0418\u0449\u0435\u0442 \u043f\u0440\u043e\u0441\u0442\u044b\u0435 \u0447\u0438\u0441\u043b\u0430 \u0434\u043e \u043c\u0438\u043b\u043b\u0438\u0430\u0440\u0434\u0430: 6.6 \u0441\u0435\u043a\u0443\u043d\u0434<\/b>.<\/p>\n
6. \u041e\u043f\u0442\u0438\u043c\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0435 \u0440\u0435\u0448\u0435\u0442\u043e \u0421\u0443\u043d\u0434\u0430\u0440\u0430\u043c\u0430<\/h2>\n
  \u041f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0430\u044f \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f \u043f\u043e\u0434\u043e\u0437\u0440\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u043f\u043e\u0445\u043e\u0436\u0430 \u043d\u0430 \u0440\u0435\u0448\u0435\u0442\u043e \u0421\u0443\u043d\u0434\u0430\u0440\u0430\u043c\u0430. \u041f\u043e \u043a\u0440\u0430\u0439\u043d\u0435\u0439 \u043c\u0435\u0440\u0435, \u043f\u0440\u043e\u0441\u0442\u044b\u0435 \u0447\u0438\u0441\u043b\u0430 \"$p$\"<\/math> \u0438 \u0442\u0430\u043c, \u0438 \u0442\u0430\u043c \u0445\u0440\u0430\u043d\u044f\u0442\u0441\u044f \u0432 \u0431\u0438\u0442\u0435 \u0441 \u043d\u043e\u043c\u0435\u0440\u043e\u043c \"$(p<\/math>. \u041f\u0440\u0438 \u044d\u0442\u043e\u043c \u0440\u0435\u0448\u0435\u0442\u043e \u0421\u0443\u043d\u0434\u0430\u0440\u0430\u043c\u0430 \u0432\u044b\u0447\u0435\u0440\u043a\u0438\u0432\u0430\u0435\u0442 \u0447\u0438\u0441\u043b\u0430 \u0432\u0438\u0434\u0430 \"$n=i+j+2ij$\"<\/math>. \u041c\u043e\u0436\u043d\u043e \u0437\u0430\u043c\u0435\u0442\u0438\u0442\u044c, \u0447\u0442\u043e \u0438\u0437 \u044d\u0442\u043e\u0433\u043e \u0441\u043b\u0435\u0434\u0443\u0435\u0442  <\/p>\n
\"$2n+1=(2i+1)(2j+1),$\"<\/math><\/p>\n
 \u0442\u043e \u0435\u0441\u0442\u044c, \u043e\u043d\u043e \u0434\u0435\u043b\u0430\u0435\u0442 \u0432 \u0442\u043e\u0447\u043d\u043e\u0441\u0442\u0438 \u0442\u043e \u0436\u0435 \u0441\u0430\u043c\u043e\u0435, \u0447\u0442\u043e \u0438 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0435 \u0440\u0435\u0448\u0435\u0442\u043e \u042d\u0440\u0430\u0442\u043e\u0441\u0444\u0435\u043d\u0430, \u0442\u043e\u043b\u044c\u043a\u043e \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u044f\u0442\u0441\u044f \u043d\u0430\u0434 \u0438\u043d\u0434\u0435\u043a\u0441\u0430\u043c\u0438 \u0431\u0438\u0442\u043e\u0432, \u0430 \u043d\u0435 \u043d\u0430\u0434 \u0441\u0430\u043c\u0438\u043c\u0438 \u0447\u0438\u0441\u043b\u0430\u043c\u0438. \u041f\u043e\u044d\u0442\u043e\u043c\u0443 \u0441\u0440\u0430\u0437\u0443 \u0441\u0442\u0430\u043d\u043e\u0432\u0438\u0442\u0441\u044f \u0432\u0438\u0434\u043d\u043e \u0440\u0430\u0437\u043b\u0438\u0447\u0438\u0435: \u0440\u0435\u0448\u0435\u0442\u043e \u042d\u0440\u0430\u0442\u043e\u0441\u0444\u0435\u043d\u0430 \u0432\u044b\u0447\u0435\u0440\u043a\u0438\u0432\u0430\u0435\u0442 \u0442\u043e\u043b\u044c\u043a\u043e \u0447\u0438\u0441\u043b\u0430, \u043a\u0440\u0430\u0442\u043d\u044b\u0435 \u043f\u0440\u043e\u0441\u0442\u044b\u043c, \u0430 \u0440\u0435\u0448\u0435\u0442\u043e \u0421\u0443\u043d\u0434\u0430\u0440\u0430\u043c\u0430 \u2014 \u043a\u0440\u0430\u0442\u043d\u044b\u0435 \u0432\u0441\u0435\u043c \u0447\u0438\u0441\u043b\u0430\u043c! \u041e\u0447\u0435\u0432\u0438\u0434\u043d\u0430\u044f \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u044f \u0440\u0435\u0448\u0435\u0442\u0430 \u0421\u0443\u043d\u0434\u0430\u0440\u0430\u043c\u0430 \u2014 \u043e\u0431\u0440\u0430\u0431\u0430\u0442\u044b\u0432\u0430\u0442\u044c \u0442\u043e\u043b\u044c\u043a\u043e \u0442\u0435 \u0447\u0438\u0441\u043b\u0430 \"$i$\"<\/math>, \u0434\u043b\u044f \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \"$2i+1$\"<\/math> \u2014 \u043f\u0440\u043e\u0441\u0442\u043e\u0435 \u0447\u0438\u0441\u043b\u043e:  <\/p>\n
    if (!Data[i]) continue; <\/code><\/pre>\n
  \u042d\u0442\u043e\u0442 \u0442\u043e\u0442 \u043d\u0435\u0447\u0430\u0441\u0442\u044b\u0439 \u0441\u043b\u0443\u0447\u0430\u0439, \u043a\u043e\u0433\u0434\u0430 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u044f \u0432 \u043e\u0434\u043d\u0443 \u0441\u0442\u0440\u043e\u0447\u043a\u0443 \u043d\u0435 \u043f\u0440\u043e\u0441\u0442\u043e \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0435\u043d\u043d\u043e \u0443\u0441\u043a\u043e\u0440\u044f\u0435\u0442 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c, \u043d\u043e \u0438 \u0443\u043b\u0443\u0447\u0448\u0430\u0435\u0442 \u0435\u0433\u043e \u0430\u0441\u0438\u043c\u043f\u0442\u043e\u0442\u0438\u0447\u0435\u0441\u043a\u0443\u044e \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c, \u0434\u0435\u043b\u0430\u044f \u0435\u0433\u043e \u043f\u0440\u0430\u043a\u0442\u0438\u0447\u0435\u0441\u043a\u0438 \u0438\u0434\u0435\u043d\u0442\u0438\u0447\u043d\u044b\u043c \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u043c\u0443 \u0440\u0435\u0448\u0435\u0442\u0443 \u042d\u0440\u0430\u0442\u043e\u0441\u0444\u0435\u043d\u0430:  <\/p>\n
                         OptimizedSieveOfSundaram.cs<\/b>                         <\/p>\n
\n
public class OptimizedSieveOfSundaram : ISieve {     private BitArray Data;     public int Length { get; private set; }      public OptimizedSieveOfSundaram(int length)     {         Length = length;         Data = new BitArray((Length + 1) \/ 2);         Data.SetAll(true);          for (int i = 1; i + i + 2 * i * i < Data.Length; i++)         {             if (!Data[i]) continue;              for (int j = i; i + j + 2 * i * j < Data.Length; j++)             {                 Data[i + j + 2 * i * j] = false;             }         }     }      public void ListPrimes(Action<long> callback)     {         callback.Invoke(2);          for (int i = 1; i < Data.Length; i++)         {             if (Data[i])             {                 int p = i * 2 + 1;                 if (p >= Length) break;                 callback.Invoke(p);             }         }     } } <\/code><\/pre>\n
  <\/div>\n<\/p><\/div>\n
  \u041f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c, \u0447\u0442\u043e \u043d\u0435 \u0443\u0434\u0438\u0432\u0438\u0442\u0435\u043b\u044c\u043d\u043e, \u0441\u043e\u0432\u043f\u0430\u0434\u0430\u0435\u0442 \u0441 \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0438\u043c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u043c:<\/p>\n
  \u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c: \u041e\u043f\u0442\u0438\u043c\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0435 \u0440\u0435\u0448\u0435\u0442\u043e \u0421\u0443\u043d\u0434\u0430\u0440\u0430\u043c\u0430<\/b>
  \u0418\u0449\u0435\u0442 \u043f\u0440\u043e\u0441\u0442\u044b\u0435 \u0447\u0438\u0441\u043b\u0430 \u0434\u043e \u043c\u0438\u043b\u043b\u0438\u0430\u0440\u0434\u0430: 6.5 \u0441\u0435\u043a\u0443\u043d\u0434<\/b>.<\/p>\n
7. \u0421\u0435\u0433\u043c\u0435\u043d\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0435 \u0440\u0435\u0448\u0435\u0442\u043e \u042d\u0440\u0430\u0442\u043e\u0441\u0444\u0435\u043d\u0430<\/h2>\n
  \u0412\u0441\u0435 \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0438\u0435 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b \u0445\u0440\u0430\u043d\u0438\u043b\u0438 \u0432\u0435\u0441\u044c \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 \u0432 \u043f\u0430\u043c\u044f\u0442\u0438, \u0447\u0442\u043e \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0438\u0432\u0430\u0435\u0442 \u0438\u0445 \u043f\u0440\u0438\u043c\u0435\u043d\u0435\u043d\u0438\u0435 \u043d\u0435\u0431\u043e\u043b\u044c\u0448\u0438\u043c\u0438 \u0434\u0438\u0430\u043f\u0430\u0437\u043e\u043d\u0430\u043c\u0438. \u041d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u043f\u0440\u0438 \u043f\u043e\u0438\u0441\u043a\u0435 \u043f\u0440\u043e\u0441\u0442\u044b\u0445 \u0447\u0438\u0441\u0435\u043b \u0434\u043e \u0442\u0440\u0438\u043b\u043b\u0438\u043e\u043d\u0430, \u0440\u0435\u0448\u0435\u0442\u043e \u042d\u0440\u0430\u0442\u043e\u0441\u0444\u0435\u043d\u0430 \u0431\u0443\u0434\u0435\u0442 \u0442\u0440\u0435\u0431\u043e\u0432\u0430\u0442\u044c 120 \u0433\u0438\u0433\u0430\u0431\u0430\u0439\u0442 \u043e\u043f\u0435\u0440\u0430\u0442\u0438\u0432\u043d\u043e\u0439 \u043f\u0430\u043c\u044f\u0442\u0438; \u043a\u0440\u043e\u043c\u0435 \u0442\u043e\u0433\u043e, \u0435\u0433\u043e \u0441\u043a\u043e\u0440\u043e\u0441\u0442\u044c \u0431\u0443\u0434\u0435\u0442 \u0434\u0435\u0433\u0440\u0430\u0434\u0438\u0440\u043e\u0432\u0430\u0442\u044c, \u0442\u0430\u043a \u043a\u0430\u043a \u043f\u0440\u043e\u0441\u0435\u0438\u0432\u0430\u043d\u0438\u0435 (\u0432\u044b\u0447\u0435\u0440\u043a\u0438\u0432\u0430\u043d\u0438\u0435 \u0441\u043e\u0441\u0442\u0430\u0432\u043d\u044b\u0445 \u0447\u0438\u0441\u0435\u043b) \u0431\u0435\u0433\u0430\u0435\u0442 \u043f\u043e \u0432\u0441\u0435\u043c\u0443 \u043c\u0430\u0441\u0441\u0438\u0432\u0443, \u043d\u0435 \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044f \u043a\u0435\u0448\u0438 \u043f\u0440\u043e\u0446\u0435\u0441\u0441\u043e\u0440\u0430.
  \u0427\u0442\u043e\u0431\u044b \u043e\u0431\u043e\u0439\u0442\u0438 \u044d\u0442\u043e \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0435, \u0432\u0441\u043f\u043e\u043c\u043d\u0438\u043c, \u0447\u0442\u043e \u0434\u043b\u044f \u043d\u0430\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u044f \u043f\u0440\u043e\u0441\u0442\u044b\u0445 \u0447\u0438\u0441\u0435\u043b \u0434\u043e \"$N$\"<\/math> \u043d\u0430\u043c \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u0432\u044b\u0447\u0435\u0440\u043a\u043d\u0443\u0442\u044c \u0447\u0438\u0441\u043b\u0430, \u043a\u0440\u0430\u0442\u043d\u044b\u0435 \u043f\u0440\u043e\u0441\u0442\u044b\u043c, \u043d\u0435 \u043f\u0440\u0435\u0432\u043e\u0441\u0445\u043e\u0434\u044f\u0449\u0438\u043c \"$\\sqrt{N}$\"<\/math>. \u042d\u0442\u043e \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u043d\u0430\u043c \u0441\u043d\u0430\u0447\u0430\u043b\u0430 \u043d\u0430\u0439\u0442\u0438 \u043f\u0440\u043e\u0441\u0442\u044b\u0435 \u0447\u0438\u0441\u043b\u0430 \u0434\u043e \"$\\sqrt{N}$\"<\/math>, \u0430 \u043f\u043e\u0442\u043e\u043c \u0440\u0430\u0437\u0431\u0438\u0442\u044c \u043e\u0442\u0440\u0435\u0437\u043e\u043a \"$[2..N]$\"<\/math> \u043d\u0430 \u043c\u0435\u043d\u044c\u0448\u0438\u0435 \u043e\u0442\u0440\u0435\u0437\u043a\u0438 (\u0441\u0435\u0433\u043c\u0435\u043d\u0442\u044b), \u0438 \u0432 \u043a\u0430\u0436\u0434\u043e\u043c \u0432\u044b\u0447\u0435\u0440\u043a\u043d\u0443\u0442\u044c \u043a\u0440\u0430\u0442\u043d\u044b\u0435 \u043f\u0440\u043e\u0441\u0442\u044b\u043c \u043f\u043e \u043e\u0442\u0434\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438. \u041d\u0430\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u0435 \u043f\u0435\u0440\u0432\u043e\u0433\u043e \u0447\u0438\u0441\u043b\u0430, \u043a\u0440\u0430\u0442\u043d\u043e\u0433\u043e \"$p$\"<\/math>, \u0432 \u0441\u0435\u0433\u043c\u0435\u043d\u0442\u0435 \u0442\u0440\u0435\u0431\u0443\u0435\u0442 \u043d\u0435\u043c\u043d\u043e\u0433\u043e \u0430\u0440\u0438\u0444\u043c\u0435\u0442\u0438\u043a\u0438:  <\/p>\n
long first = p * p; if (first < segmentStart) {     first += (segmentStart - first + p - 1) \/ p * p; }<\/code><\/pre>\n
  \u0432\u044b\u0447\u0435\u0440\u043a\u0438\u0432\u0430\u0435\u043c \u043a\u0440\u0430\u0442\u043d\u044b\u0435 2: [ 80<\/s>, 81, 82<\/s>, 83, 84<\/s>, 85, 86<\/s>, 87, 88<\/s>, 89, 90<\/s>]
  \u0432\u044b\u0447\u0435\u0440\u043a\u0438\u0432\u0430\u0435\u043c \u043a\u0440\u0430\u0442\u043d\u044b\u0435 3: [ 81<\/s>, 83, 85, 87<\/s>, 89]
  \u0432\u044b\u0447\u0435\u0440\u043a\u0438\u0432\u0430\u0435\u043c \u043a\u0440\u0430\u0442\u043d\u044b\u0435 5: [83, 85<\/s>, 89]
  \u0432\u044b\u0447\u0435\u0440\u043a\u0438\u0432\u0430\u0435\u043c \u043a\u0440\u0430\u0442\u043d\u044b\u0435 7 (\u043d\u0435\u0442 \u0432 \u0438\u043d\u0442\u0435\u0440\u0432\u0430\u043b\u0435): [83, 89]<\/code>
  \u042d\u0442\u043e\u0442 \u043f\u043e\u0434\u0445\u043e\u0434 \u043d\u0430\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u0441\u0435\u0433\u043c\u0435\u043d\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0435 \u0440\u0435\u0448\u0435\u0442\u043e<\/a>, \u0438 \u0441 \u0435\u0433\u043e \u043f\u0440\u0438\u043c\u0435\u043d\u0435\u043d\u0438\u0435\u043c \u0442\u0440\u0435\u0431\u043e\u0432\u0430\u043d\u0438\u044f \u043a \u043f\u0430\u043c\u044f\u0442\u0438 \u0441\u043d\u0438\u0436\u0430\u044e\u0442\u0441\u044f \u0441 \"$O(N)$\"<\/math> \u0434\u043e \"$O(\\sqrt{N})$\"<\/math>. \u041d\u0430 \u043f\u0440\u0430\u043a\u0442\u0438\u043a\u0435 \u0440\u0430\u0437\u043c\u0435\u0440 \u0438\u043d\u0442\u0435\u0440\u0432\u0430\u043b\u043e\u0432 \u0432\u044b\u0431\u0438\u0440\u0430\u044e\u0442 \u043b\u0438\u0431\u043e \u0440\u0430\u0432\u043d\u044b\u043c \"$\\sqrt{N}$\"<\/math>, \u043b\u0438\u0431\u043e \u0437\u0430\u0432\u0438\u0441\u044f\u0449\u0438\u043c \u043e\u0442 \u0440\u0430\u0437\u043c\u0435\u0440\u0430 \u043a\u0435\u0448\u0430 \u043f\u0440\u043e\u0446\u0435\u0441\u0441\u043e\u0440\u0430.  <\/p>\n
                         SegmentedSieveOfEratosthenes.cs<\/b>                         <\/p>\n
\n
public class SegmentedSieveOfEratosthenes : ISieve {     private long Length;     private int FirstChunkLength;     private long[] FirstPrimes;      public SegmentedSieveOfEratosthenes(long length)     {         Length = length;         FirstChunkLength = (int)Math.Sqrt(length) + 1;         SieveOfEratosthenes sieve = new SieveOfEratosthenes(FirstChunkLength);         List<long> firstPrimes = new List<long>();         sieve.ListPrimes(firstPrimes.Add);         FirstPrimes = firstPrimes.ToArray();     }      private void SieveSegment(BitArray segmentData, long segmentStart, long segmentEnd)     {         segmentData.SetAll(true);          foreach (long p in FirstPrimes)         {             long first = p * p;             if (first < segmentStart)             {                 first += (segmentStart - first + p - 1) \/ p * p;             }              for (long i = first; i < segmentEnd; i += p)             {                 segmentData[(int)(i - segmentStart)] = false;             }         }     }      public void ListPrimes(Action<long> callback)     {         foreach (long p in FirstPrimes) callback.Invoke(p);          int segmentLength = FirstChunkLength;         BitArray segmentData = new BitArray(segmentLength);         long segmentStart = FirstChunkLength;         long segmentEnd = Math.Min(segmentStart + segmentLength, Length);         while (segmentStart < Length)         {             SieveSegment(segmentData, segmentStart, segmentEnd);             for (long i = segmentStart; i < segmentEnd; i++)             {                 if (segmentData[(int)(i - segmentStart)]) callback.Invoke(i);             }             segmentStart = segmentEnd;             segmentEnd = Math.Min(segmentStart + segmentLength, Length);         }     } } <\/code><\/pre>\n
  <\/div>\n<\/p><\/div>\n
  \u0417\u0430 \u0441\u0447\u0435\u0442 \u043b\u0443\u0447\u0448\u0435\u0433\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u044f \u043a\u0435\u0448\u0430 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u0431\u044b\u0441\u0442\u0440\u0435\u0435 \u043e\u0431\u044b\u0447\u043d\u043e\u0433\u043e \u0440\u0435\u0448\u0435\u0442\u0430 \u042d\u0440\u0430\u0442\u043e\u0441\u0444\u0435\u043d\u0430 \u043d\u0430 \u0442\u0435\u0445 \u0436\u0435 \u0434\u0430\u043d\u043d\u044b\u0445:<\/p>\n
  \u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c: \u0421\u0435\u0433\u043c\u0435\u043d\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0435 \u0440\u0435\u0448\u0435\u0442\u043e \u042d\u0440\u0430\u0442\u043e\u0441\u0444\u0435\u043d\u0430<\/b>
  \u0418\u0449\u0435\u0442 \u043f\u0440\u043e\u0441\u0442\u044b\u0435 \u0447\u0438\u0441\u043b\u0430 \u0434\u043e \u043c\u0438\u043b\u043b\u0438\u0430\u0440\u0434\u0430: 8.6 \u0441\u0435\u043a\u0443\u043d\u0434<\/b>.<\/p>\n
8. \u041e\u043f\u0442\u0438\u043c\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0435 \u0441\u0435\u0433\u043c\u0435\u043d\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0435 \u0440\u0435\u0448\u0435\u0442\u043e<\/h2>\n
  \u0414\u0430\u043d\u043d\u0430\u044f \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u044f \u043e\u0442\u043d\u043e\u0441\u0438\u0442\u0441\u044f \u043a \u00ab\u043d\u0430\u0440\u043e\u0434\u043d\u043e\u0439\u00bb \u2014 \u043e\u043d\u0430 \u0448\u0438\u0440\u043e\u043a\u043e \u0438\u0437\u0432\u0435\u0441\u0442\u043d\u0430, \u043d\u043e, \u043f\u043e\u0445\u043e\u0436\u0435, \u043d\u0435 \u0438\u043c\u0435\u0435\u0442 \u0441\u0432\u043e\u0435\u0433\u043e \u043d\u0430\u0437\u0432\u0430\u043d\u0438\u044f. \u0426\u0435\u043b\u044c \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u0438 \u2014 \u0438\u0437\u0431\u0430\u0432\u0438\u0442\u044c\u0441\u044f \u043e\u0442 \u0430\u0440\u0438\u0444\u043c\u0435\u0442\u0438\u0447\u0435\u0441\u043a\u043e\u0433\u043e \u0432\u044b\u0440\u0430\u0436\u0435\u043d\u0438\u044f, \u0432\u044b\u0447\u0438\u0441\u043b\u044f\u044e\u0449\u0435\u0433\u043e \u043f\u0435\u0440\u0432\u043e\u0435 \u0447\u0438\u0441\u043b\u043e \u0432 \u0441\u0435\u0433\u043c\u0435\u043d\u0442\u0435, \u043a\u0440\u0430\u0442\u043d\u043e\u0435 \u043f\u0440\u043e\u0441\u0442\u043e\u043c\u0443 \u0447\u0438\u0441\u043b\u0443 \"$p$\"<\/math>. \u0422\u0430\u043a \u043a\u0430\u043a \u0441\u0435\u0433\u043c\u0435\u043d\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0435 \u0440\u0435\u0448\u0435\u0442\u043e \u043e\u0431\u0440\u0430\u0431\u0430\u0442\u044b\u0432\u0430\u0435\u0442 \u0441\u0435\u0433\u043c\u0435\u043d\u0442\u044b \u043f\u043e\u0434\u0440\u044f\u0434 \u0432 \u043f\u043e\u0440\u044f\u0434\u043a\u0435 \u0432\u043e\u0437\u0440\u0430\u0441\u0442\u0430\u043d\u0438\u044f, \u043d\u0435\u0442\u0440\u0443\u0434\u043d\u043e \u0443\u0431\u0435\u0434\u0438\u0442\u044c\u0441\u044f, \u0447\u0442\u043e \u043d\u0443\u0436\u043d\u043e\u0435 \u0447\u0438\u0441\u043b\u043e \u0431\u0443\u0434\u0435\u0442 \u0440\u0430\u0432\u043d\u043e \u043f\u0435\u0440\u0432\u043e\u043c\u0443 \u0447\u0438\u0441\u043b\u0443, \u043a\u0440\u0430\u0442\u043d\u043e\u043c\u0443 \"$p$\"<\/math>, \u0432\u044b\u0445\u043e\u0436\u044f\u0449\u0435\u043c\u0443 \u0437\u0430 \u0433\u0440\u0430\u043d\u0438\u044b \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0435\u0433\u043e \u0441\u0435\u0433\u043c\u0435\u043d\u0442\u0430. \u0422\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c, \u043d\u0430\u043c \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u043f\u0440\u043e\u0441\u0442\u043e\u0433\u043e \u0447\u0438\u0441\u043b\u0430 \"$p<=\\sqrt{N}$\"<\/math> \u0445\u0440\u0430\u043d\u0438\u0442\u044c \u0442\u0435\u043a\u0443\u0449\u0435\u0435 \u043a\u0440\u0430\u0442\u043d\u043e\u0435 \u0435\u043c\u0443 \u0447\u0438\u0441\u043b\u043e. \u0412 \u0443\u043f\u0440\u043e\u0449\u0435\u043d\u043d\u043e\u043c \u0432\u0438\u0434\u0435 \u044d\u0442\u043e \u043c\u043e\u0436\u043d\u043e \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u0438\u0442\u044c \u0442\u0430\u043a:  <\/p>\n
long[] PrimeMultiples = FirstPrimes.Select(p => p * p).ToArray(); ... while(PrimeMultiples[i] < segmentEnd) {     segmentData[PrimeMultiples[i] - segmentStart] = false;     PrimeMultiples[i] += FirstPrimes[i]; } <\/code><\/pre>\n
  \u041f\u043e\u043b\u043d\u0430\u044f \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f \u0441 \u043d\u0435\u0431\u043e\u043b\u044c\u0448\u0438\u043c\u0438 \u0434\u043e\u043f\u043e\u043b\u043d\u0438\u0442\u0435\u043b\u044c\u043d\u044b\u043c\u0438 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u044f\u043c\u0438 \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u0443\u0441\u043a\u043e\u0440\u0438\u0442\u044c \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0438\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043f\u0440\u0438\u043c\u0435\u0440\u043d\u043e \u043d\u0430 20%  <\/p>\n
                         OptimizedSegmentedSieve.cs<\/b>                         <\/p>\n
\n
public class OptimizedSegmentedSieve : ISieve {     const int BUFFER_LENGTH = 64 * 1024;     private long Length;     private long[] FirstPrimes;     private long[] PrimeMultiples;      public OptimizedSegmentedSieve(long length)     {         Length = length;         int firstChunkLength = (int)Math.Sqrt(length) + 1;         SieveOfEratosthenes sieve = new SieveOfEratosthenes(firstChunkLength);         List<long> firstPrimes = new List<long>();         sieve.ListPrimes(firstPrimes.Add);         FirstPrimes = firstPrimes.ToArray();         PrimeMultiples = FirstPrimes.Select(p => p * p).ToArray();     }      private void SieveSegment(BitArray segmentData, long segmentStart, long segmentEnd)     {         segmentData.SetAll(true);         long segmentLength = segmentEnd - segmentStart;         for (int i = 0; i < PrimeMultiples.Length; i++)         {             long current = PrimeMultiples[i] - segmentStart;             long prime = FirstPrimes[i];             if (current >= segmentLength) continue;              while (current < segmentLength)             {                 segmentData[(int)current] = false;                 current += prime;             }             PrimeMultiples[i] = segmentStart + current;         }     }      public void ListPrimes(Action<long> callback)     {         BitArray segmentData = new BitArray(BUFFER_LENGTH);         long segmentStart = 2;         long segmentEnd = Math.Min(segmentStart + BUFFER_LENGTH, Length);         while (segmentStart < Length)         {             SieveSegment(segmentData, segmentStart, segmentEnd);             for (int i = 0; i < segmentEnd - segmentStart; i++)             {                 if (segmentData[i]) callback.Invoke(segmentStart + i);             }             segmentStart = segmentEnd;             segmentEnd = Math.Min(segmentStart + BUFFER_LENGTH, Length);         }     } } <\/code><\/pre>\n
  <\/div>\n<\/p><\/div>\n
  \u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c: \u041e\u043f\u0442\u0438\u043c\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0435 \u0441\u0435\u0433\u043c\u0435\u043d\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0435 \u0440\u0435\u0448\u0435\u0442\u043e<\/b>
  \u0418\u0449\u0435\u0442 \u043f\u0440\u043e\u0441\u0442\u044b\u0435 \u0447\u0438\u0441\u043b\u0430 \u0434\u043e \u043c\u0438\u043b\u043b\u0438\u0430\u0440\u0434\u0430: 7.1 \u0441\u0435\u043a\u0443\u043d\u0434<\/b>.<\/p>\n
9. \u0421\u0435\u0433\u043c\u0435\u043d\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u0430\u044f \u0444\u0430\u043a\u0442\u043e\u0440\u0438\u0437\u0430\u0446\u0438\u044f \u0441 \u0431\u0430\u0437\u043e\u0439 2<\/h2>\n
  \u0420\u0430\u043d\u044c\u0448\u0435 \u043c\u044b \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u043b\u0438 \u043e\u043f\u0442\u0438\u043c\u0437\u0430\u0446\u0438\u044e, \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u044e\u0449\u0443\u044e \u0445\u0440\u0430\u043d\u0438\u0442\u044c \u0442\u043e\u043b\u044c\u043a\u043e \u043d\u0435\u0447\u0435\u0442\u043d\u044b\u0435 \u0447\u0438\u0441\u043b\u0430, \u0438 \u043d\u0438\u0447\u0435\u0433\u043e \u043d\u0430\u043c \u043d\u0435 \u043c\u0435\u0448\u0430\u0435\u0442 \u043f\u0440\u0438\u043c\u0435\u043d\u0438\u0442\u044c \u0435\u0435 \u043a \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0435\u043c\u0443 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0443. \u0422\u043e\u043b\u044c\u043a\u043e \u0442\u0435\u043f\u0435\u0440\u044c \u043c\u0430\u0441\u0441\u0438\u0432 PrimeMultiples \u0431\u0443\u0434\u0435\u0442 \u0445\u0440\u0430\u043d\u0438\u0442\u044c \u043d\u0435 \"$p^2<\/math>, \u0430 \"$((p^2<\/math>:  <\/p>\n
long[] PrimeMultiples = FirstPrimes.Select(p => (p * p - 1) \/ 2).ToArray(); ... while(PrimeMultiples[i] < segmentEnd) {     segmentData[PrimeMultiples[i] - segmentStart] = false;     PrimeMultiples[i] += FirstPrimes[i]; } <\/code><\/pre>\n
  \u0418\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u043e, \u0447\u0442\u043e \u043e\u0441\u043d\u043e\u0432\u043d\u043e\u0439 \u0446\u0438\u043a\u043b \u0438\u0441\u043a\u043b\u044e\u0447\u0435\u043d\u0438\u044f \u0441\u043e\u0441\u0442\u0430\u0432\u043d\u044b\u0445 \u0447\u0438\u0441\u0435\u043b \u043d\u0435 \u0438\u0437\u043c\u0435\u043d\u0438\u043b\u0441\u044f, \u0440\u0430\u0437\u043d\u0438\u0446\u0430 \u0442\u043e\u043b\u044c\u043a\u043e \u0432 \u0438\u043d\u0438\u0446\u0438\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438 \u043c\u0430\u0441\u0441\u0438\u0432\u0430 PrimeMultiples \u0438 \u0432 \u043f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u043e\u0432\u0430\u043d\u0438\u0438 \u0438\u043d\u0434\u0435\u043a\u0441\u0430 \u0431\u0438\u0442\u043e\u0432 \u0432 \u0447\u0438\u0441\u043b\u043e \u043f\u043e \u0437\u043d\u0430\u043a\u043e\u043c\u043e\u0439 \u043d\u0430\u043c \u0444\u043e\u0440\u043c\u0443\u043b\u0435 \"$p=2i+1$\"<\/math>.   <\/p>\n
                         SegmentedWheel2.cs<\/b>                         <\/p>\n
\n
public class SegmentedWheel2 : ISieve {     const int BUFFER_LENGTH = 64 * 1024;     private long Length;     private long[] FirstPrimes;     private long[] PrimeMultiples;      public SegmentedWheel2(long length)     {         Length = length;         int firstChunkLength = (int)Math.Sqrt(length) + 1;         SieveOfEratosthenes sieve = new SieveOfEratosthenes(firstChunkLength);         List<long> firstPrimes = new List<long>();         sieve.ListPrimes(firstPrimes.Add);         FirstPrimes = firstPrimes.Skip(1).ToArray();         PrimeMultiples = FirstPrimes.Select(p => (p * p - 1) \/ 2).ToArray();     }      private void SieveSegment(BitArray segmentData, long segmentStart, long segmentEnd)     {         segmentData.SetAll(true);         long segmentLength = segmentEnd - segmentStart;         for (int i = 0; i < PrimeMultiples.Length; i++)         {             long current = PrimeMultiples[i] - segmentStart;             long prime = FirstPrimes[i];             if (current >= segmentLength) continue;              while (current < segmentLength)             {                 segmentData[(int)current] = false;                 current += prime;             }             PrimeMultiples[i] = segmentStart + current;         }     }      public void ListPrimes(Action<long> callback)     {         callback.Invoke(2);         BitArray segmentData = new BitArray(BUFFER_LENGTH);         long max = Length \/ 2;         long segmentStart = 1;         long segmentEnd = Math.Min(segmentStart + BUFFER_LENGTH, max);         while (segmentStart < max)         {             SieveSegment(segmentData, segmentStart, segmentEnd);             for (int i = 0; i < segmentEnd - segmentStart; i++)             {                 if (segmentData[i])                 {                     callback.Invoke((segmentStart + i) * 2 + 1);                 }             }             segmentStart = segmentEnd;             segmentEnd = Math.Min(segmentStart + BUFFER_LENGTH, max);         }     } } <\/code><\/pre>\n
  <\/div>\n<\/p><\/div>\n
  \u042d\u0442\u0430 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u044f \u0443\u0441\u043a\u043e\u0440\u044f\u0435\u0442 \u043f\u043e\u0438\u0441\u043a \u043f\u0440\u043e\u0441\u0442\u044b\u0445 \u0447\u0438\u0441\u0435\u043b \u0431\u043e\u043b\u044c\u0449\u0435, \u0447\u0435\u043c \u0432\u0434\u0432\u043e\u0435:<\/p>\n
  \u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c: \u0421\u0435\u0433\u043c\u0435\u043d\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u0430\u044f \u0444\u0430\u043a\u0442\u043e\u0440\u0438\u0437\u0430\u0446\u0438\u044f \u0441 \u0431\u0430\u0437\u043e\u0439 2<\/b>
  \u0418\u0449\u0435\u0442 \u043f\u0440\u043e\u0441\u0442\u044b\u0435 \u0447\u0438\u0441\u043b\u0430 \u0434\u043e \u043c\u0438\u043b\u043b\u0438\u0430\u0440\u0434\u0430: 3.4 \u0441\u0435\u043a\u0443\u043d\u0434\u044b<\/b>.<\/p>\n
10. \u0421\u0435\u0433\u043c\u0435\u043d\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u0430\u044f (2,3)-\u0444\u0430\u043a\u0442\u043e\u0440\u0438\u0437\u0430\u0446\u0438\u044f<\/h2>\n
  \u0412 \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0435\u0439 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438 \u043c\u044b \u0438\u0441\u043a\u043b\u044e\u0447\u0438\u043b\u0438 \u0438\u0437 \u0440\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0435\u043d\u0438\u044f \u0447\u0438\u0441\u043b\u0430, \u0434\u0435\u043b\u044f\u0449\u0438\u0435\u0441\u044f \u043d\u0430 \u0434\u0432\u0430; \u0442\u0435\u043f\u0435\u0440\u044c \u0438\u0441\u043a\u043b\u044e\u0447\u0438\u043c \u0447\u0438\u0441\u043b\u0430, \u0434\u0435\u043b\u044f\u0449\u0438\u0435\u0441\u044f \u043d\u0430 2 \u0438 3. \u0422\u043e\u0433\u0434\u0430 \u043e\u0441\u0442\u0430\u0432\u0448\u0438\u0435\u0441\u044f \u0447\u0438\u0441\u043b\u0430 \u0434\u0435\u043b\u044f\u0442\u0441\u044f \u043d\u0430 \u0434\u0432\u0430 \u043a\u043b\u0430\u0441\u0441\u0430: \u0434\u0430\u044e\u0449\u0438\u0435 1 \u0438\u043b\u0438 5 \u0432 \u043e\u0441\u0442\u0430\u0442\u043a\u0435 \u043e\u0442 \u0434\u0435\u043b\u0435\u043d\u0438\u044f \u043d\u0430 6. \u041f\u043e\u044d\u0442\u043e\u043c\u0443 \u0432\u043c\u0435\u0441\u0442\u043e \u043e\u0434\u043d\u043e\u0433\u043e \u0431\u0438\u0442\u043e\u0432\u043e\u0433\u043e \u043c\u0430\u0441\u0441\u0438\u0432\u0430 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u043c \u0434\u0432\u0430: PrimeMultiples_6kPlus1 \u0438 PrimeMultiples_6kPlus5; \u043e\u043d\u0438 \u0431\u0443\u0434\u0443\u0442 \u0445\u0440\u0430\u043d\u0438\u0442\u044c \u0447\u0438\u0441\u043b\u0430 \u0432\u0438\u0434\u0430 \"$(n<\/math> \u0438 \"$(n<\/math> \u0434\u043b\u044f \u0447\u0438\u0441\u0435\u043b, \u043a\u0440\u0430\u0442\u043d\u044b\u0445 \"$p$\"<\/math>, \u0438\u043c\u0435\u044e\u0449\u0438\u0445 1 \u0438\u043b\u0438 5 \u0432 \u043e\u0441\u0442\u0430\u0442\u043a\u0435 \u043e\u0442 \u0434\u0435\u043b\u0435\u043d\u0438\u044f \u043d\u0430 6. \u0414\u043e\u043f\u043e\u043b\u043d\u0438\u0442\u0435\u043b\u044c\u043d\u044b\u0435 \u0443\u0441\u0438\u043b\u0438\u044f \u043d\u0443\u0436\u043d\u044b, \u0447\u0442\u043e\u0431\u044b \u043d\u0430\u0439\u0442\u0438 \u043f\u0435\u0440\u0432\u043e\u0435 \u0447\u0438\u0441\u043b\u043e \u0432\u0438\u0434\u0430 \"$p^2+kp$\"<\/math>, \u0438\u043c\u0435\u044e\u0449\u0435\u0435 \u043d\u0443\u0436\u043d\u044b\u0439 \u043e\u0441\u0442\u0430\u0442\u043e\u043a \u043e\u0442 \u0434\u0435\u043b\u0435\u043d\u0438\u044f \u043d\u0430 6, \u043d\u043e \u044d\u0442\u043e \u0440\u0435\u0448\u0430\u0435\u0442\u0441\u044f \u043f\u0440\u043e\u0441\u0442\u044b\u043c \u043f\u0435\u0440\u0435\u0431\u043e\u0440\u043e\u043c \"$k=0,<\/math>.  <\/p>\n
                         SegmentedWheel23.cs<\/b>                         <\/p>\n
\n
public class SegmentedWheel23 : ISieve {     const int BUFFER_LENGTH = 128 * 1024;      private long Length;     private long[] FirstPrimes;     private long[] PrimeMultiples_6kPlus1;     private long[] PrimeMultiples_6kPlus5;      public SegmentedWheel23(long length)     {         Length = length;         int firstChunkLength = (int)Math.Sqrt(length) + 1;         SieveOfEratosthenes sieve = new SieveOfEratosthenes(firstChunkLength);         List<long> firstPrimes = new List<long>();         sieve.ListPrimes(firstPrimes.Add);         FirstPrimes = firstPrimes.Skip(2).ToArray();         PrimeMultiples_6kPlus1 = new long[FirstPrimes.Length];         PrimeMultiples_6kPlus5 = new long[FirstPrimes.Length];         for (int j = 0; j < FirstPrimes.Length; j++)         {             long prime = FirstPrimes[j];             long val1 = prime * prime;             while (val1 % 6 != 1) val1 += 2 * prime;             PrimeMultiples_6kPlus1[j] = (val1 - 1) \/ 6;             long val2 = prime * prime;             while (val2 % 6 != 5) val2 += 2 * prime;             PrimeMultiples_6kPlus5[j] = (val2 - 5) \/ 6;         }     }      private void SieveSegment(BitArray segmentData_6kPlus1, BitArray segmentData_6kPlus5, long segmentStart, long segmentEnd)     {         segmentData_6kPlus1.SetAll(true);         segmentData_6kPlus5.SetAll(true);         long segmentLength = segmentEnd - segmentStart;         for (int j = 0; j < FirstPrimes.Length; j++)         {             long prime = FirstPrimes[j];              long val1 = PrimeMultiples_6kPlus1[j] - segmentStart;             while (val1 < segmentLength)             {                 segmentData_6kPlus1[(int)val1] = false;                 val1 += prime;             }             PrimeMultiples_6kPlus1[j] = val1 + segmentStart;              long val2 = PrimeMultiples_6kPlus5[j] - segmentStart;             while (val2 < segmentLength)             {                 segmentData_6kPlus5[(int)val2] = false;                 val2 += prime;             }             PrimeMultiples_6kPlus5[j] = val2 + segmentStart;         }     }      public void ListPrimes(Action<long> callback)     {         callback.Invoke(2);         callback.Invoke(3);         callback.Invoke(5);         BitArray segmentData_6kPlus1 = new BitArray(BUFFER_LENGTH);         BitArray segmentData_6kPlus5 = new BitArray(BUFFER_LENGTH);         long max = (Length + 5) \/ 6;         long segmentStart = 1;         long segmentEnd = Math.Min(segmentStart + BUFFER_LENGTH, max);         while (segmentStart < max)         {             SieveSegment(segmentData_6kPlus1, segmentData_6kPlus5, segmentStart, segmentEnd);             for (int i = 0; i < segmentEnd - segmentStart; i++)             {                 if (segmentData_6kPlus1[i])                 {                     long p = (segmentStart + i) * 6 + 1;                     if (p >= Length) break;                     callback.Invoke(p);                 }                 if (segmentData_6kPlus5[i])                 {                     long p = (segmentStart + i) * 6 + 5;                     if (p >= Length) break;                     callback.Invoke(p);                  }             }             segmentStart = segmentEnd;             segmentEnd = Math.Min(segmentStart + BUFFER_LENGTH, max);         }     } } <\/code><\/pre>\n
  <\/div>\n<\/p><\/div>\n
  \u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c: \u0421\u0435\u0433\u043c\u0435\u043d\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u0430\u044f (2,3)-\u0444\u0430\u043a\u0442\u043e\u0440\u0438\u0437\u0430\u0446\u0438\u044f<\/b>
  \u0418\u0449\u0435\u0442 \u043f\u0440\u043e\u0441\u0442\u044b\u0435 \u0447\u0438\u0441\u043b\u0430 \u0434\u043e \u043c\u0438\u043b\u043b\u0438\u0430\u0440\u0434\u0430: 2.6 \u0441\u0435\u043a\u0443\u043d\u0434\u044b<\/b>.<\/p>\n
11. \u0421\u0435\u0433\u043c\u0435\u043d\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u0430\u044f (2,3,5)-\u0444\u0430\u043a\u0442\u043e\u0440\u0438\u0437\u0430\u0446\u0438\u044f<\/h2>\n
  \u041f\u0440\u0438\u043c\u0435\u043d\u0438\u043c \u0442\u0443 \u0436\u0435 \u0438\u0434\u0435\u044e \u0434\u043b\u044f \u0447\u0438\u0441\u0435\u043b, \u043d\u0435 \u0434\u0435\u043b\u044f\u0449\u0438\u0445\u0441\u044f \u043d\u0430 2, 3 \u0438 5. \u0422\u043e\u0433\u0434\u0430 \u0443 \u043d\u0430\u0441 \u0431\u0443\u0434\u0435\u0442 \u043d\u0435 \u0434\u0432\u0430 \u0431\u0438\u0442\u043e\u0432\u044b\u0445 \u043c\u0430\u0441\u0441\u0438\u0432\u0430, \u0430 \u0432\u043e\u0441\u0435\u043c\u044c, \u043f\u043e \u043e\u0434\u043d\u043e\u043c\u0443 \u043d\u0430 \u043a\u0430\u0436\u0434\u044b\u0439 \u043e\u0441\u0442\u0430\u0442\u043e\u043a \u043e\u0442 \u0434\u0435\u043b\u0435\u043d\u0438\u044f \u043d\u0430 30: \"$(1,<\/math>. \u0412 \u043e\u0441\u0442\u0430\u043b\u044c\u043d\u043e\u043c \u043a\u043e\u0434 \u043d\u0435 \u043e\u0441\u043e\u0431\u043e \u0438\u0437\u043c\u0435\u043d\u0438\u0442\u0441\u044f, \u0438 \u0434\u0430\u0441\u0442 \u043d\u0430\u043c \u0435\u0449\u0435 \u043d\u0435\u0431\u043e\u043b\u044c\u0448\u043e\u0435 \u0443\u0441\u043a\u043e\u0440\u0435\u043d\u0438\u0435.  <\/p>\n
                         SegmentedWheel235.cs<\/b>                         <\/p>\n
\n
public class SegmentedWheel235 : ISieve {     const int BUFFER_LENGTH = 128 * 1024;     const int WHEEL = 30;     const int WHEEL_PRIMES_COUNT = 3;     private long[] WheelRemainders = { 1, 7, 11, 13, 17, 19, 23, 29 };     private long[] SkipPrimes = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 };      private long Length;     private long[] FirstPrimes;     private long[][] PrimeMultiples;      public SegmentedWheel235(long length)     {         Length = length;         int firstChunkLength = (int)Math.Sqrt(length) + 1;         SieveOfEratosthenes sieve = new SieveOfEratosthenes(firstChunkLength);         List<long> firstPrimes = new List<long>();         sieve.ListPrimes(firstPrimes.Add);         FirstPrimes = firstPrimes.Skip(WHEEL_PRIMES_COUNT).ToArray();         PrimeMultiples = new long[WheelRemainders.Length][];         for (int i = 0; i < WheelRemainders.Length; i++)         {             PrimeMultiples[i] = new long[FirstPrimes.Length];             for (int j = 0; j < FirstPrimes.Length; j++)             {                 long prime = FirstPrimes[j];                 long val = prime * prime;                 while (val % WHEEL != WheelRemainders[i]) val += 2 * prime;                 PrimeMultiples[i][j] = (val - WheelRemainders[i]) \/ WHEEL;             }         }     }      private void SieveSegment(BitArray[] segmentDatas, long segmentStart, long segmentEnd)     {         for (int i = 0; i < segmentDatas.Length; i++)         {             BitArray segmentData = segmentDatas[i];             segmentData.SetAll(true);             long segmentLength = segmentEnd - segmentStart;             for (int j = 0; j < PrimeMultiples[i].Length; j++)             {                 long current = PrimeMultiples[i][j] - segmentStart;                 long prime = FirstPrimes[j];                 if (current >= segmentLength) continue;                  while (current < segmentLength)                 {                     segmentData[(int)current] = false;                     current += prime;                 }                 PrimeMultiples[i][j] = segmentStart + current;             }         }     }      public void ListPrimes(Action<long> callback)     {         foreach (long prime in SkipPrimes) if (prime < Length) callback.Invoke(prime);          BitArray[] segmentDatas = new BitArray[WheelRemainders.Length];         for (int i = 0; i < segmentDatas.Length; i++)         {             segmentDatas[i] = new BitArray(BUFFER_LENGTH);         }         long max = (Length + WHEEL - 1) \/ WHEEL;         long segmentStart = 1;         long segmentEnd = Math.Min(segmentStart + BUFFER_LENGTH, max);         while (segmentStart < max)         {             SieveSegment(segmentDatas, segmentStart, segmentEnd);             for (int i = 0; i < segmentEnd - segmentStart; i++)             {                 long offset = (segmentStart + i) * WHEEL;                 for (int j = 0; j < segmentDatas.Length; j++)                 {                     if (segmentDatas[j][i])                     {                         long p = offset + WheelRemainders[j];                         if (p >= Length) break;                         callback.Invoke(p);                     }                 }             }             segmentStart = segmentEnd;             segmentEnd = Math.Min(segmentStart + BUFFER_LENGTH, max);         }     } } <\/code><\/pre>\n
  <\/div>\n<\/p><\/div>\n
  \u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c: \u0421\u0435\u0433\u043c\u0435\u043d\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u0430\u044f (2,3,5)-\u0444\u0430\u043a\u0442\u043e\u0440\u0438\u0437\u0430\u0446\u0438\u044f<\/b>
  \u0418\u0449\u0435\u0442 \u043f\u0440\u043e\u0441\u0442\u044b\u0435 \u0447\u0438\u0441\u043b\u0430 \u0434\u043e \u043c\u0438\u043b\u043b\u0438\u0430\u0440\u0434\u0430: 2.3 \u0441\u0435\u043a\u0443\u043d\u0434\u044b<\/b>.<\/p>\n
12. \u041e\u043f\u0442\u0438\u043c\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u0430\u044f \u0441\u0435\u0433\u043c\u0435\u043d\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u0430\u044f (2,3,5)-\u0444\u0430\u043a\u0442\u043e\u0440\u0438\u0437\u0430\u0446\u0438\u044f<\/h2>\n
  \u0424\u0430\u043a\u0442\u043e\u0440\u0438\u0437\u0430\u0446\u0438\u044f \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u0443\u043c\u0435\u043d\u044c\u0448\u0438\u0442\u044c \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0447\u0438\u0441\u0435\u043b, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043c\u044b \u0432\u044b\u0447\u0435\u0440\u043a\u0438\u0432\u0430\u0435\u043c, \u043d\u043e \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u0435 \u0438\u043d\u0434\u0435\u043a\u0441\u0430 \u0431\u0430\u0439\u0442\u0430 \u0438 \u0431\u0438\u0442\u0430 \u0432 \u0431\u0438\u0442\u043e\u0432\u043e\u043c \u043c\u0430\u0441\u0441\u0438\u0432\u0435 (\u043a\u0430\u043a \u043f\u0440\u0438 \u043f\u0440\u043e\u0441\u0435\u0438\u0432\u0430\u043d\u0438\u0438, \u0442\u0430\u043a \u0438 \u043f\u0440\u0438 \u043f\u043e\u0432\u0442\u043e\u0440\u043d\u043e\u043c \u043f\u0440\u043e\u0445\u043e\u0434\u0435 \u043f\u043e \u043c\u0430\u0441\u0441\u0438\u0432\u0443 \u0434\u043b\u044f \u043f\u0435\u0440\u0435\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f \u043f\u0440\u043e\u0441\u0442\u044b\u0445 \u0447\u0438\u0441\u0435\u043b) \u0432\u0441\u0435 \u0440\u0430\u0432\u043d\u043e \u0437\u0430\u043d\u0438\u043c\u0430\u0435\u0442 \u0431\u043e\u043b\u044c\u0448\u0443\u044e \u0447\u0430\u0441\u0442\u044c \u0432\u0440\u0435\u043c\u0435\u043d\u0438. \u041f\u043e\u044d\u0442\u043e\u043c\u0443 \u0432\u043e\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u043c\u0441\u044f \u0443\u0436\u0435 \u0437\u043d\u0430\u043a\u043e\u043c\u044b\u043c \u043d\u0430\u043c \u0442\u0440\u044e\u043a\u043e\u043c, \u043f\u043e\u043b\u044c\u0437\u0443\u044f\u0441\u044c \u0442\u0435\u043c, \u0447\u0442\u043e \u0432 \u0444\u0430\u043a\u0442\u043e\u0440\u0438\u0437\u0430\u0446\u0438\u0438 \u0441 \u0431\u0430\u0437\u043e\u0439 (2,3,5) \u0432\u043e\u0441\u0435\u043c\u044c \u043e\u0441\u0442\u0430\u0442\u043a\u043e\u0432: \u0432\u043c\u0435\u0441\u0442\u043e \u0432\u043e\u0441\u044c\u043c\u0438 \u0431\u0438\u0442\u043e\u0432\u044b\u0445 \u043c\u0430\u0441\u0441\u0438\u0432\u043e\u0432 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u043c \u043e\u0434\u0438\u043d \u043c\u0430\u0441\u0441\u0438\u0432 \u0431\u0430\u0439\u0442, \u0432 \u043a\u043e\u0442\u043e\u0440\u043e\u043c \u043a\u0430\u0436\u0434\u044b\u0439 \u0438\u0437 \u0432\u043e\u0441\u044c\u043c\u0438 \u0431\u0438\u0442 \u043e\u0442\u0432\u0435\u0447\u0430\u0435\u0442 \u0437\u0430 \u0441\u0432\u043e\u0439 \u043e\u0441\u0442\u0430\u0442\u043e\u043a \u043e\u0442 \u0434\u0435\u043b\u0435\u043d\u0438\u044f \u043d\u0430 30. \u042d\u0442\u043e \u043f\u043e\u0437\u0432\u043e\u043b\u0438\u0442 \u043d\u0430\u043c \u0432 \u043c\u0430\u0441\u0441\u0438\u0432\u0435 PrimeMultiples \u0434\u0435\u0440\u0436\u0430\u0442\u044c \u0438\u043d\u0434\u0435\u043a\u0441 \u0431\u0430\u0439\u0442\u0430<\/b>, \u0430 \u0438\u043d\u0434\u0435\u043a\u0441 \u0431\u0438\u0442\u0430 \u0431\u0443\u0434\u0435\u0442 \u043f\u043e\u0441\u0442\u043e\u044f\u043d\u043d\u044b\u043c. \u0422\u043e\u0433\u0434\u0430 \u0432\u043d\u0443\u0442\u0440\u0435\u043d\u043d\u0438\u0439 \u0446\u0438\u043a\u043b \u043f\u0440\u043e\u0441\u0435\u0438\u0432\u0430\u043d\u0438\u044f \u0441\u0442\u0430\u043d\u043e\u0432\u0438\u0442\u0441\u044f \u0438\u0441\u043a\u043b\u044e\u0447\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u043f\u0440\u043e\u0441\u0442\u044b\u043c:  <\/p>\n
while (current < segmentLength) {     segmentData[current] &= mask;     current += prime; } <\/code><\/pre>\n
  \u041f\u0440\u0438 \u0442\u0430\u043a\u043e\u043c \u043f\u043e\u0434\u0445\u043e\u0434\u0435 \u043f\u043e\u0432\u0442\u043e\u0440\u043d\u044b\u0439 \u043f\u0440\u043e\u0445\u043e\u0434 \u043f\u043e \u043c\u0430\u0441\u0441\u0438\u0432\u0443 \u0443\u0436\u0435 \u0437\u0430\u043d\u0438\u043c\u0430\u0435\u0442 \u0431\u043e\u043b\u044c\u0448\u0435 \u0432\u0440\u0435\u043c\u0435\u043d\u0438, \u043f\u043e\u0441\u043a\u043e\u043b\u044c\u043a\u0443 \u0442\u0440\u0435\u0431\u0443\u0435\u0442 \u0431\u043e\u043b\u044c\u0448\u0435 \u0431\u0438\u0442\u043e\u0432\u044b\u0445 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439. \u041e\u0434\u043d\u0430\u043a\u043e \u043b\u044e\u0431\u043e\u0439 \u0431\u0430\u0439\u0442 \u043c\u043e\u0436\u0435\u0442 \u043f\u0440\u0438\u043d\u0438\u043c\u0430\u0442\u044c \u0432\u0441\u0435\u0433\u043e 256 \u0432\u0430\u0440\u0438\u0430\u043d\u0442\u043e\u0432, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u043c\u044b \u043c\u043e\u0436\u0435\u043c \u0437\u0430\u0440\u0430\u043d\u0435\u0435 \u0432\u044b\u0447\u0438\u0441\u043b\u0438\u0442\u044c \u0432\u0441\u0435 256 \u043a\u043e\u043c\u0431\u0438\u043d\u0430\u0446\u0438\u0439 \u043e\u0441\u0442\u0430\u0442\u043a\u043e\u0432, \u0438 \u0432\u043e\u043e\u0431\u0449\u0435 \u0438\u0437\u0431\u0430\u0432\u0438\u0442\u044c\u0441\u044f \u043e\u0442 \u0431\u0438\u0442\u043e\u0432\u044b\u0445 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439. \u041d\u0430\u043f\u0440\u0438\u043c\u0435\u0440:
  \u0431\u0430\u0439\u0442 = 255 = 0b11111111, \u043e\u0441\u0442\u0430\u0442\u043a\u0438: [1, 7, 11, 13, 17, 19, 23, 29]
  \u0431\u0430\u0439\u0442 = 9 = 0b00001001, \u043e\u0441\u0442\u0430\u0442\u043a\u0438: [1, 13]
  \u0431\u0430\u0439\u0442 = 135 = 0b10000111, \u043e\u0441\u0442\u0430\u0442\u043a\u0438: [1, 7, 11, 29]<\/code>
  \u0422\u043e\u0433\u0434\u0430 \u043f\u043e\u043b\u0443\u0447\u0435\u043d\u0438\u0435 \u043f\u0440\u043e\u0441\u0442\u044b\u0445 \u0447\u0438\u0441\u0435\u043b \u0441\u0432\u043e\u0434\u0438\u0442\u0441\u044f \u043a \u043f\u0440\u043e\u0441\u0442\u043e\u043c\u0443 \u0446\u0438\u043a\u043b\u0443:   <\/p>\n
for (int i = 0; i < segmentData.Length; i++) {     byte data = segmentData[i];     int[] offsets = OffsetsPerByte[data];     for (int j = 0; j < offsets.Length; j++)     {         long p = (segmentStart + i) * 30 + offsets[j];         if (p >= Length) break;         callback.Invoke(p);     } } <\/code><\/pre>\n
  \u042d\u0442\u0430 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u044f \u0443\u0441\u043a\u043e\u0440\u044f\u0435\u0442 \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0443\u044e \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044e \u0431\u043e\u043b\u044c\u0448\u0435, \u0447\u0435\u043c \u0432 \u0434\u0432\u0430 \u0440\u0430\u0437\u0430, \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u044f \u043d\u0430\u0439\u0442\u0438 \u043f\u0440\u043e\u0441\u0442\u044b\u0435 \u0447\u0438\u0441\u043b\u0430 \u0434\u043e \u043c\u0438\u043b\u043b\u0438\u0430\u0440\u0434\u0430 \u043c\u0435\u043d\u044c\u0448\u0435, \u0447\u0435\u043c \u0437\u0430 \u0441\u0435\u043a\u0443\u043d\u0434\u0443!  <\/p>\n
                         OptimizedSegmentedWheel235.cs<\/b>                         <\/p>\n
\n
public class OptimizedSegmentedWheel235 : ISieve {     const int BUFFER_LENGTH = 200 * 1024;     const int WHEEL = 30;     const int WHEEL_PRIMES_COUNT = 3;      private static long[] WheelRemainders = { 1, 7, 11, 13, 17, 19, 23, 29 };     private static long[] SkipPrimes = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 };     private static byte[] Masks = { 1, 2, 4, 8, 16, 32, 64, 128 };     private static int[][] OffsetsPerByte;      private long Length;     private long[] FirstPrimes;     private long[][] PrimeMultiples;      static OptimizedSegmentedWheel235()     {         OffsetsPerByte = new int[256][];         List<int> offsets = new List<int>();         for (int b = 0; b < 256; b++)         {             offsets.Clear();             for (int i = 0; i < WheelRemainders.Length; i++)             {                 if ((b & Masks[i]) != 0) offsets.Add((int)WheelRemainders[i]);             }             OffsetsPerByte[b] = offsets.ToArray();         }     }      public OptimizedSegmentedWheel235(long length)     {         Length = length;         int firstChunkLength = (int)Math.Sqrt(length) + 1;         SieveOfEratosthenes sieve = new SieveOfEratosthenes(firstChunkLength);         List<long> firstPrimes = new List<long>();         sieve.ListPrimes(firstPrimes.Add);         FirstPrimes = firstPrimes.Skip(WHEEL_PRIMES_COUNT).ToArray();         PrimeMultiples = new long[WheelRemainders.Length][];         for (int i = 0; i < WheelRemainders.Length; i++)         {             PrimeMultiples[i] = new long[FirstPrimes.Length];             for (int j = 0; j < FirstPrimes.Length; j++)             {                 long prime = FirstPrimes[j];                 long val = prime * prime;                 while (val % WHEEL != WheelRemainders[i]) val += 2 * prime;                 PrimeMultiples[i][j] = (val - WheelRemainders[i]) \/ WHEEL;             }         }     }      private void SieveSegment(byte[] segmentData, long segmentStart, long segmentEnd)     {         for (int i = 0; i < segmentData.Length; i++) segmentData[i] = 255;         long segmentLength = segmentEnd - segmentStart;          for (int i = 0; i < WheelRemainders.Length; i++)         {             byte mask = (byte)~Masks[i];             for (int j = 0; j < PrimeMultiples[i].Length; j++)             {                 long current = PrimeMultiples[i][j] - segmentStart;                 if (current >= segmentLength) continue;                 long prime = FirstPrimes[j];                  while (current < segmentLength)                 {                     segmentData[current] &= mask;                     current += prime;                 }                  PrimeMultiples[i][j] = segmentStart + current;             }         }     }      public void ListPrimes(Action<long> callback)     {         foreach (long prime in SkipPrimes) if (prime < Length) callback.Invoke(prime);          long max = (Length + WHEEL - 1) \/ WHEEL;         byte[] segmentData = new byte[BUFFER_LENGTH];         long segmentStart = 1;         long segmentEnd = Math.Min(segmentStart + BUFFER_LENGTH, max);         while (segmentStart < max)         {             SieveSegment(segmentData, segmentStart, segmentEnd);             for (int i = 0; i < segmentData.Length; i++)             {                 long offset = (segmentStart + i) * WHEEL;                 byte data = segmentData[i];                 int[] offsets = OffsetsPerByte[data];                 for (int j = 0; j < offsets.Length; j++)                 {                     long p = offset + offsets[j];                     if (p >= Length) break;                     callback.Invoke(p);                 }             }             segmentStart = segmentEnd;             segmentEnd = Math.Min(segmentStart + BUFFER_LENGTH, max);         }     } } <\/code><\/pre>\n
  <\/div>\n<\/p><\/div>\n
  \u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c: \u041e\u043f\u0442\u0438\u043c\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u0430\u044f \u0441\u0435\u0433\u043c\u0435\u043d\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u0430\u044f (2,3,5)-\u0444\u0430\u043a\u0442\u043e\u0440\u0438\u0437\u0430\u0446\u0438\u044f<\/b>
  \u0418\u0449\u0435\u0442 \u043f\u0440\u043e\u0441\u0442\u044b\u0435 \u0447\u0438\u0441\u043b\u0430 \u0434\u043e \u043c\u0438\u043b\u043b\u0438\u0430\u0440\u0434\u0430: 0.93 \u0441\u0435\u043a\u0443\u043d\u0434\u044b<\/b>.<\/p>\n
\u041c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u043c\u0435\u0436\u0434\u0443 \u043f\u0440\u043e\u0441\u0442\u044b\u043c\u0438 \u0447\u0438\u0441\u043b\u0430\u043c\u0438 \u0434\u043e \u0442\u0440\u0438\u043b\u043b\u0438\u043e\u043d\u0430<\/h2>\n
  \u0418\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044f \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u044e\u044e \u0432\u0435\u0440\u0441\u0438\u044e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430, \u043b\u0435\u0433\u043a\u043e \u043d\u0430\u043f\u0438\u0441\u0430\u0442\u044c \u043f\u0440\u043e\u0441\u0442\u043e\u0439 \u043a\u043e\u0434, \u0441\u043a\u0430\u043d\u0438\u0440\u0443\u044e\u0449\u0438\u0439 \u043f\u0440\u043e\u0441\u0442\u044b\u0435 \u0447\u0438\u0441\u043b\u0430 \u0434\u043e \u0442\u0440\u0438\u043b\u043b\u0438\u043e\u043d\u0430 \u0438 \u0438\u0449\u0443\u0449\u0438\u0439 \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u043c\u0435\u0436\u0434\u0443 \u0441\u043e\u0441\u0435\u0434\u043d\u0438\u043c\u0438 \u043f\u0440\u043e\u0441\u0442\u044b\u043c\u0438 \u0447\u0438\u0441\u043b\u0430\u043c\u0438:  <\/p>\n
static void Main(string[] args) {     var sieve = new OptimizedSegmentedWheel235(1_000_000_000_000);     long maxDistance = 0;     long lastPrime = 0;     Action<long> action = (p) =>     {         long dist = p - lastPrime;         if (dist > maxDistance)         {             Console.WriteLine($"{p} - {lastPrime} = {dist}");             maxDistance = dist;         }         lastPrime = p;     };     sieve.ListPrimes(action); } <\/code><\/pre>\n
  \u0420\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 \u0440\u0430\u0431\u043e\u0442\u044b \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u044b:
  \u041f\u0440\u043e\u0441\u0442\u044b\u0435 \u0447\u0438\u0441\u043b\u0430 \u0434\u043e 1,000,000,000,000<\/b>
  \u0412\u0440\u0435\u043c\u044f \u0440\u0430\u0431\u043e\u0442\u044b: 26 \u043c\u0438\u043d\u0443\u0442 30 \u0441\u0435\u043a\u0443\u043d\u0434<\/b>
  \u041c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u043c\u0435\u0436\u0434\u0443 \u043f\u0440\u043e\u0441\u0442\u044b\u043c\u0438 \u0447\u0438\u0441\u043b\u0430\u043c\u0438: 540<\/b>
  \u043c\u0435\u0436\u0434\u0443 738,832,927,927 \u0438 738,832,928,467 <\/p>\n
\u041b\u0443\u0447\u0448\u0438\u0435 \u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a\u0438<\/h2>\n
  \u0420\u0430\u0441\u0441\u043a\u0430\u0437 \u0431\u044b\u043b \u0431\u044b \u043d\u0435 \u043f\u043e\u043b\u043e\u043d \u0431\u0435\u0437 \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u044f \u0441 \u043b\u0443\u0447\u0448\u0438\u043c\u0438 \u0438\u0437 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u044e\u0449\u0438\u0445 \u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a \u043f\u043e \u043f\u043e\u0438\u0441\u043a\u0443 \u043f\u0440\u043e\u0441\u0442\u044b\u0445 \u0447\u0438\u0441\u0435\u043b.
  \u0421\u0430\u043c\u0430\u044f \u0438\u0437\u0432\u0435\u0441\u0442\u043d\u0430\u044f \u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a\u0430 \u2014 primegen<\/a>, \u043e\u0441\u043d\u043e\u0432\u0430\u043d\u043d\u0430\u044f \u043d\u0430 \u0441\u0438\u043b\u044c\u043d\u043e \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u043c \u0440\u0435\u0448\u0435\u0442\u0435 \u0410\u0442\u043a\u0438\u043d\u0430. \u041e\u043d\u0430 \u043d\u0430\u043f\u0438\u0441\u0430\u043d\u0430 \u043d\u0430 C \u0441\u0430\u043c\u0438\u043c \u0414\u0430\u043d\u0438\u044d\u043b\u0435\u043c \u0411\u0435\u0440\u043d\u0448\u0442\u0435\u0439\u043d\u043e\u043c (\u0441\u043e\u0430\u0432\u0442\u043e\u0440\u043e\u043c \u0410\u0442\u043a\u0438\u043d\u0430) 20 \u043b\u0435\u0442 \u043d\u0430\u0437\u0430\u0434 \u0438 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u043d\u0430 \u043f\u043e\u0434 \u041f\u0435\u043d\u0442\u0438\u0443\u043c, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u0434\u043b\u044f \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u043e\u0433\u043e \u0435\u0435 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u044f \u0442\u0440\u0435\u0431\u0443\u0435\u0442\u0441\u044f \u043f\u043e\u043c\u0435\u043d\u044f\u0442\u044c \u0440\u0430\u0437\u043c\u0435\u0440 \u0431\u0443\u0444\u0435\u0440\u0430 \u0432 \u0444\u0430\u0439\u043b\u0435 conf-words:
  2048
  This is B\/32: the number of 32-bit words of space used in the primegen
  inner loop. This should fit into the CPU's level-1 cache.<\/p>\n
  2048 works well on a Pentium-100.
  3600 works well on a Pentium II-350.
  4004 works well on an UltraSPARC-I\/167.
  <\/code>
  \u041d\u0430 \u043c\u043e\u0435\u043c \u043d\u043e\u0443\u0442\u0431\u0443\u043a\u0435 \u043d\u0430\u0438\u043b\u0443\u0447\u0448\u0430\u044f \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c \u0434\u043e\u0441\u0442\u0438\u0433\u0430\u0435\u0442\u0441\u044f \u043f\u0440\u0438 \u0443\u0441\u0442\u0430\u043d\u043e\u0432\u043a\u0435 \u0431\u0443\u0444\u0435\u0440\u0430 65536 \u0431\u0430\u0439\u0442. \u0412 \u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a\u0443 \u0432\u0445\u043e\u0434\u0438\u0442 \u0443\u0442\u0438\u043b\u0438\u0442\u0430 primegaps, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u043a\u0430\u043a \u0440\u0430\u0437 \u0438 \u0438\u0449\u0435\u0442 \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u043c\u0435\u0436\u0434\u0443 \u043f\u0440\u043e\u0441\u0442\u044b\u043c\u0438 \u0447\u0438\u0441\u043b\u0430\u043c\u0438. \u0412\u0440\u0435\u043c\u044f \u0435\u0435 \u0440\u0430\u0431\u043e\u0442\u044b \u0434\u043b\u044f \u043f\u0440\u043e\u0441\u0442\u044b\u0445 \u0447\u0438\u0441\u0435\u043b \u0434\u043e \u0442\u0440\u0438\u043b\u043b\u0438\u043e\u043d\u0430 \u2014 19 \u043c\u0438\u043d\u0443\u0442.<\/p>\n
  \u041d\u043e \u043d\u0430 \u0434\u0430\u043d\u043d\u044b\u0439 \u043c\u043e\u043c\u0435\u043d\u0442, \u043f\u043e\u0436\u0430\u043b\u0443\u0439, \u0441\u0430\u043c\u0430\u044f \u0431\u044b\u0441\u0442\u0440\u0430\u044f \u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a\u0430 \u2014 primesieve<\/a>, \u043d\u0430\u043f\u0438\u0441\u0430\u043d\u043d\u0430\u044f \u043d\u0430 c++ \u0438 \u0432\u043a\u043b\u044e\u0447\u0430\u044e\u0449\u0430\u044f \u043e\u0433\u0440\u043e\u043c\u043d\u043e\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u0439, \u0432\u043a\u043b\u044e\u0447\u0430\u044f \u0440\u0430\u0437\u043b\u0438\u0447\u043d\u044b\u0435 \u0441\u0442\u0440\u0430\u0442\u0435\u0433\u0438\u0438 \u043f\u0440\u043e\u0441\u0435\u0438\u0432\u0430\u043d\u0438\u044f \u0434\u043b\u044f \u043c\u0430\u043b\u0435\u043d\u044c\u043a\u0438\u0445, \u0441\u0440\u0435\u0434\u043d\u0438\u0445 \u0438 \u0431\u043e\u043b\u044c\u0448\u0438\u0445 \u043f\u0440\u043e\u0441\u0442\u044b\u0445 \u0447\u0438\u0441\u0435\u043b, \u0430\u0432\u0442\u043e\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u043e\u0435 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u0435 \u0440\u0430\u0437\u043c\u0435\u0440\u0430 \u043a\u0435\u0448\u0435\u0439 \u043f\u0440\u043e\u0446\u0435\u0441\u0441\u043e\u0440\u0430 \u0438 \u043c\u043d\u043e\u0433\u043e\u043f\u043e\u0442\u043e\u0447\u043d\u043e\u0441\u0442\u044c. \u041d\u0430 \u043c\u043e\u0435\u043c \u043d\u043e\u0443\u0442\u0431\u0443\u043a\u0435 \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0430 \u0438\u0449\u0435\u0442 \u043f\u0440\u043e\u0441\u0442\u044b\u0435 \u0447\u0438\u0441\u043b\u0430 \u0434\u043e \u0442\u0440\u0438\u043b\u043b\u0438\u043e\u043d\u0430 \u0432 8 \u043f\u043e\u0442\u043e\u043a\u043e\u0432 \u0437\u0430 70 \u0441\u0435\u043a\u0443\u043d\u0434. \u0410\u0432\u0442\u043e\u0440 \u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a\u0438 Kim Walish \u043f\u043e\u0434\u0440\u043e\u0431\u043d\u043e \u043e\u043f\u0438\u0441\u044b\u0432\u0430\u0435\u0442 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u0438 \u0432 \u043a\u043e\u0434\u0435<\/a>, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u044d\u0442\u0430 \u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a\u0430 \u043e\u0442\u043b\u0438\u0447\u043d\u043e \u043f\u043e\u0434\u0445\u043e\u0434\u0438\u0442 \u0434\u043b\u044f \u0438\u0437\u0443\u0447\u0435\u043d\u0438\u044f \u0441\u0430\u043c\u044b\u0445 \u043b\u0443\u0447\u0448\u0438\u0445 \u043d\u0430 \u0441\u0435\u0433\u043e\u0434\u043d\u044f\u0448\u043d\u0438\u0439 \u0434\u0435\u043d\u044c \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u0439 \u0438 \u0434\u043b\u044f \u043f\u0440\u0430\u043a\u0442\u0438\u0447\u0435\u0441\u043a\u043e\u0433\u043e \u043f\u0440\u0438\u043c\u0435\u043d\u0435\u043d\u0438\u044f.<\/div>\n
 \u0441\u0441\u044b\u043b\u043a\u0430 \u043d\u0430 \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b \u0441\u0442\u0430\u0442\u044c\u0438  https:\/\/habr.com\/ru\/post\/526924\/<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"\n
\"image\"<\/p>\n
  \u041f\u043e\u0438\u0441\u043a \u043f\u0440\u043e\u0441\u0442\u044b\u0445 \u0447\u0438\u0441\u0435\u043b \u2014 \u043f\u043e\u043f\u0443\u043b\u044f\u0440\u043d\u0430\u044f \u0437\u0430\u0434\u0430\u0447\u0430 \u0441\u0440\u0435\u0434\u0438 \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0441\u0442\u043e\u0432, \u0443\u0432\u043b\u0435\u043a\u0430\u044e\u0449\u0438\u0445\u0441\u044f \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u043a\u043e\u0439. \u0421\u0430\u043c\u044b\u0439 \u0438\u0437\u0432\u0435\u0441\u0442\u043d\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c, \u043f\u0440\u0438\u0434\u0443\u043c\u0430\u043d\u043d\u044b\u0439, \u043f\u043e-\u0432\u0438\u0434\u0438\u043c\u043e\u043c\u0443, \u0431\u043e\u043b\u044c\u0448\u0435 \u0434\u0432\u0443\u0445 \u0442\u044b\u0441\u044f\u0447 \u043b\u0435\u0442 \u043d\u0430\u0437\u0430\u0434, \u2014 \u0440\u0435\u0448\u0435\u0442\u043e \u042d\u0440\u0430\u0442\u043e\u0441\u0444\u0435\u043d\u0430<\/a>; \u0432 \u043d\u0430\u0441\u0442\u043e\u044f\u0449\u0435\u0435 \u0432\u0440\u0435\u043c\u044f \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442 \u0431\u0435\u0441\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u043e\u0435 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e \u0435\u0433\u043e \u0432\u0430\u0440\u0438\u0430\u043d\u0442\u043e\u0432 \u0438 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u0439. 
  \u0421\u0435\u0433\u043e\u0434\u043d\u044f \u044f \u0445\u043e\u0442\u0435\u043b \u0431\u044b \u043f\u043e\u0434\u0435\u043b\u0438\u0442\u044c\u0441\u044f \u0441 \u0432\u0430\u043c\u0438 \u0440\u0430\u0437\u043b\u0438\u0447\u043d\u044b\u043c\u0438 \u0432\u0430\u0440\u0438\u0430\u043d\u0442\u0430\u043c\u0438 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438 \u043f\u043e\u0438\u0441\u043a\u0430 \u043f\u0440\u043e\u0441\u0442\u044b\u0445 \u0447\u0438\u0441\u0435\u043b \u043d\u0430 \u044f\u0437\u044b\u043a\u0435 C#, \u043d\u0430\u0447\u0438\u043d\u0430\u044f \u0441 \u043a\u043b\u0430\u0441\u0441\u0438\u0447\u0435\u0441\u043a\u0438\u0445 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u0432 \u2014 \u0440\u0435\u0448\u0435\u0442\u0430 \u042d\u0440\u0430\u0442\u043e\u0441\u0444\u0435\u043d\u0430, \u0421\u0443\u043d\u0434\u0430\u0440\u0430\u043c\u0430 \u0438 \u0410\u0442\u043a\u0438\u043d\u0430, \u0438 \u043a\u043e\u043d\u0447\u0430\u044f \u0440\u0430\u0437\u043b\u0438\u0447\u043d\u044b\u043c\u0438 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u044f\u043c\u0438 (\u0441\u0435\u0433\u043c\u0435\u043d\u0442\u0430\u0446\u0438\u044f, \u0444\u0430\u043a\u0442\u043e\u0440\u0438\u0437\u0430\u0446\u0438\u044f). \u041e\u0441\u043e\u0431\u044b\u0439 \u0443\u043f\u043e\u0440 \u044f \u0434\u0435\u043b\u0430\u043b \u043d\u0430 \u043f\u0440\u043e\u0441\u0442\u043e\u0442\u0443: \u0441\u0430\u043c\u044b\u0439 \u0431\u044b\u0441\u0442\u0440\u044b\u0439 \u0438\u0437 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u0432, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043c\u043d\u0435 \u0443\u0434\u0430\u043b\u043e\u0441\u044c \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c, \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442 120 \u0441\u0442\u0440\u043e\u043a \u043a\u043e\u0434\u0430 \u0438 \u0438\u0449\u0435\u0442 \u043f\u0440\u043e\u0441\u0442\u044b\u0435 \u0447\u0438\u0441\u043b\u0430 \u0434\u043e \u0442\u0440\u0438\u043b\u043b\u0438\u043e\u043d\u0430 \u043c\u0435\u043d\u044c\u0448\u0435, \u0447\u0435\u043c \u0437\u0430 30 \u043c\u0438\u043d\u0443\u0442, \u0430 \u0434\u043e \u043c\u0438\u043b\u043b\u0438\u0430\u0440\u0434\u0430 \u2014 \u043c\u0435\u043d\u044c\u0448\u0435, \u0447\u0435\u043c \u0437\u0430 \u0441\u0435\u043a\u0443\u043d\u0434\u0443 (\u044d\u0442\u043e \u0434\u0430\u043b\u0435\u043a\u043e \u043e\u0442 \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438 \u043b\u0443\u0447\u0448\u0438\u0445 \u0438\u0437 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u044e\u0449\u0438\u0445 \u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a \u043f\u043e \u043f\u043e\u0438\u0441\u043a\u0443 \u043f\u0440\u043e\u0441\u0442\u044b\u0445 \u0447\u0438\u0441\u0435\u043b, \u043d\u043e \u044d\u0442\u0438 \u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a\u0438 \u043e\u0431\u044b\u0447\u043d\u043e \u0441\u043e\u0434\u0435\u0440\u0436\u0430\u0442 \u0441\u0432\u044b\u0448\u0435 4000 \u0441\u0442\u0440\u043e\u043a \u043a\u043e\u0434\u0430).
  \u0412 \u0437\u0430\u043a\u043b\u044e\u0447\u0435\u043d\u0438\u0435 \u043c\u044b \u043f\u0440\u0438\u043c\u0435\u043d\u0438\u043c \u0441\u0430\u043c\u0443\u044e \u0431\u044b\u0441\u0442\u0440\u0443\u044e \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044e \u0434\u043b\u044f \u043f\u043e\u0438\u0441\u043a\u0430 \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u044f \u043c\u0435\u0436\u0434\u0443 \u0434\u0432\u0443\u043c\u044f \u0441\u043e\u0441\u0435\u0434\u043d\u0438\u043c\u0438 \u043f\u0440\u043e\u0441\u0442\u044b\u043c\u0438 \u0447\u0438\u0441\u043b\u0430\u043c\u0438 \u0434\u043e \u0442\u0440\u0438\u043b\u043b\u0438\u043e\u043d\u0430. \u041f\u0440\u0435\u0436\u0434\u0435 \u0447\u0435\u043c \u0437\u0430\u0445\u043e\u0434\u0438\u0442\u044c \u043f\u043e\u0434 \u043a\u0430\u0442, \u044f \u043f\u0440\u0435\u0434\u043b\u0430\u0433\u0430\u044e \u0432\u0430\u043c \u043f\u043e\u043f\u044b\u0442\u0430\u0442\u044c\u0441\u044f \u0443\u0433\u0430\u0434\u0430\u0442\u044c \u043e\u0442\u0432\u0435\u0442. \u0414\u043b\u044f \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u044f, \u0434\u043b\u044f \u043f\u0440\u043e\u0441\u0442\u044b\u0445 \u0447\u0438\u0441\u0435\u043b \u0434\u043e 100 \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u0440\u0430\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u0440\u0430\u0432\u043d\u043e 8 (\u043c\u0435\u0436\u0434\u0443 \u0441\u043e\u0441\u0435\u0434\u043d\u0438\u043c\u0438 \u043f\u0440\u043e\u0441\u0442\u044b\u043c\u0438 \u0447\u0438\u0441\u043b\u0430\u043c\u0438 89 \u0438 97), \u0430 \u0434\u043e \u0442\u044b\u0441\u044f\u0447\u0438 \u2014 20 (\u043c\u0435\u0436\u0434\u0443 887 \u0438 907).
  \u0412\u0435\u0441\u044c \u0438\u0441\u0445\u043e\u0434\u043d\u044b\u0439 \u043a\u043e\u0434 \u043c\u043e\u0436\u043d\u043e \u043d\u0430\u0439\u0442\u0438 \u043d\u0430 \u0433\u0438\u0442\u0445\u0430\u0431\u0435<\/a>.  <\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[],"tags":[],"class_list":["post-312881","post","type-post","status-publish","format-standard","hentry"],"_links":{"self":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/312881","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=312881"}],"version-history":[{"count":0,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/312881\/revisions"}],"wp:attachment":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=312881"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=312881"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=312881"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}