{"id":285709,"date":"2017-04-29T01:05:16","date_gmt":"2017-04-28T21:05:16","guid":{"rendered":"http:\/\/savepearlharbor.com\/?p=285709"},"modified":"-0001-11-30T00:00:00","modified_gmt":"-0001-11-29T21:00:00","slug":"","status":"publish","type":"post","link":"https:\/\/savepearlharbor.com\/?p=285709","title":{"rendered":"\u0411\u044b\u0441\u0442\u0440\u043e\u0435 \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u0435 \u0444\u0430\u043a\u0442\u043e\u0440\u0438\u0430\u043b\u0430 \u2014 PrimeSwing"},"content":{"rendered":"<p>\u041d\u0430\u0442\u043a\u043d\u0443\u0432\u0448\u0438\u0441\u044c \u043d\u0435\u0434\u0430\u0432\u043d\u043e \u043d\u0430 <a href=\"https:\/\/habrahabr.ru\/post\/327544\/\">\u044d\u0442\u0443 \u0441\u0442\u0430\u0442\u044c\u044e<\/a>, \u044f \u043f\u043e\u043d\u044f\u043b, \u0447\u0442\u043e \u0440\u0435\u0434\u043a\u043e \u0443\u043f\u043e\u043c\u0438\u043d\u0430\u044e\u0442\u0441\u044f \u0441\u043f\u043e\u0441\u043e\u0431\u044b \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f \u0444\u0430\u043a\u0442\u043e\u0440\u0438\u0430\u043b\u0430, \u043e\u0442\u043b\u0438\u0447\u043d\u044b\u0435 \u043e\u0442 \u0431\u0430\u043d\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u043f\u0435\u0440\u0435\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u044f \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u0445 \u0447\u0438\u0441\u0435\u043b. \u041d\u0443\u0436\u043d\u043e \u044d\u0442\u0443 \u0441\u0438\u0442\u0443\u0430\u0446\u0438\u044e \u0438\u0441\u043f\u0440\u0430\u0432\u0438\u0442\u044c.<br \/>  \u041f\u0440\u0435\u0434\u043b\u0430\u0433\u0430\u044e \u0440\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0435\u0442\u044c \u00ab\u0430\u0441\u0438\u043c\u043f\u0442\u043e\u0442\u0438\u0447\u0435\u0441\u043a\u0438 \u043d\u0430\u0438\u0431\u043e\u043b\u0435\u0435 \u0431\u044b\u0441\u0442\u0440\u044b\u0439\u00bb \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f \u0444\u0430\u043a\u0442\u043e\u0440\u0438\u0430\u043b\u0430!<a name=\"habracut\"><\/a><\/p>\n<p>  \u0414\u043b\u044f \u043d\u0430\u0447\u0430\u043b\u0430 \u043d\u0430\u043f\u043e\u043c\u043d\u044e, \u0447\u0442\u043e \u0444\u0430\u043a\u0442\u043e\u0440\u0438\u0430\u043b n \u2014 \u044d\u0442\u043e \u043f\u0440\u043e\u0438\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u0435 \u0432\u0441\u0435\u0445 \u043d\u0430\u0442\u0443\u0440\u0430\u043b\u044c\u043d\u044b\u0445 \u0447\u0438\u0441\u0435\u043b \u043e\u0442 1 \u0434\u043e n (<math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/f92\/0d7\/e75\/f920d7e75bcada66f68642f6ea8ff289.svg\" alt=\"$n!=1\\cdot2\\cdot\\ldots\\cdot n$\" data-tex=\"inline\"\/><\/math>), \u043f\u0440\u0438 \u044d\u0442\u043e\u043c <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/85a\/9ca\/8c6\/85a9ca8c6c436795240c28e047f6927a.svg\" alt=\"$0!=1$\" data-tex=\"inline\"\/><\/math>;<\/p>\n<h3>1. \u0414\u0435\u043a\u043e\u043c\u043f\u043e\u0437\u0438\u0446\u0438\u044f \u0444\u0430\u043a\u0442\u043e\u0440\u0438\u0430\u043b\u0430<\/h3>\n<p>  \u0412\u0432\u0435\u0434\u0451\u043c \u0444\u0443\u043d\u043a\u0446\u0438\u044e, \u0438\u043c\u0435\u043d\u0443\u0435\u043c\u0443\u044e <i>swinging factorial<\/i>, \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c:  <\/p>\n<p><math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/d72\/766\/751\/d727667515eb866775f25af32faadcd1.svg\" alt=\"$n\\wr=\\frac{n!}{\\lfloor n\/2\\rfloor!^2}$\" data-tex=\"display\"\/><\/math><\/p>\n<p>  \u0414\u0430\u043d\u043d\u0430\u044f \u0434\u0440\u043e\u0431\u044c \u0432\u0441\u0435\u0433\u0434\u0430 \u0431\u0443\u0434\u0435\u0442 \u0446\u0435\u043b\u044b\u043c \u0447\u0438\u0441\u043b\u043e\u043c \u043f\u043e \u043f\u0440\u043e\u0441\u0442\u043e\u0439 \u043f\u0440\u0438\u0447\u0438\u043d\u0435 \u2014 \u043e\u043d\u0430 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0434\u0435\u043b\u0438\u0442\u0435\u043b\u0435\u043c \u0446\u0435\u043d\u0442\u0440\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u0431\u0438\u043d\u043e\u043c\u0438\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u043a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442\u0430 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/bb7\/5d2\/52b\/bb75d252b42411217f00978c35e2b346.svg\" alt=\"$\\binom{n}{\\lfloor n\/2\\rfloor}$\" data-tex=\"inline\"\/><\/math>, \u0440\u0430\u0432\u043d\u043e\u0433\u043e<\/p>\n<p><math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/433\/c0a\/bf4\/433c0abf45c2bc7249147c27c8111449.svg\" alt=\"$\\binom{n}{\\lfloor n\/2\\rfloor}=\\frac{n!}{\\lfloor n\/2\\rfloor!\\cdot\\lceil n\/2\\rceil!}$\" data-tex=\"display\"\/><\/math><\/p>\n<p>  \u0420\u0430\u0437\u0432\u043e\u0440\u0430\u0447\u0438\u0432\u0430\u044f \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u0435 <i>swinging factorial<\/i>, \u043c\u044b \u043f\u043e\u043b\u0443\u0447\u0438\u043c \u043d\u043e\u0432\u0443\u044e \u0440\u0435\u043a\u0443\u0440\u0440\u0435\u043d\u0442\u043d\u0443\u044e \u0444\u043e\u0440\u043c\u0443\u043b\u0443 \u0444\u0430\u043a\u0442\u043e\u0440\u0438\u0430\u043b\u0430:<\/p>\n<p><math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/7b2\/629\/764\/7b2629764f8464c0fb98e0e1aec7a564.svg\" alt=\"$n!=\\lfloor n\/2\\rfloor!^2\\cdot n\\wr$\" data-tex=\"display\"\/><\/math><\/p>\n<p>  \u041e\u043d\u0430 \u0431\u0443\u0434\u0435\u0442 \u043e\u0441\u043e\u0431\u0435\u043d\u043d\u043e \u0445\u043e\u0440\u043e\u0448\u0430, \u0435\u0441\u043b\u0438 \u043c\u044b \u043d\u0430\u0443\u0447\u0438\u043c\u0441\u044f \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u043e \u0432\u044b\u0447\u0438\u0441\u043b\u044f\u0442\u044c \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/6d5\/92f\/b9f\/6d592fb9fbd278de0c91af9e724605da.svg\" alt=\"$n\\wr$\" data-tex=\"inline\"\/><\/math>.<\/p>\n<h3>2. \u041f\u0440\u043e\u0441\u0442\u044b\u0435 \u043c\u043d\u043e\u0436\u0438\u0442\u0435\u043b\u0438 <i>swinging factorial<\/i><\/h3>\n<p>  \u041e\u0431\u043e\u0437\u043d\u0430\u0447\u0438\u043c <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/6a8\/3f2\/521\/6a83f2521026f8873e864be5c3378bab.svg\" alt=\"$l_p(n\\wr)$\" data-tex=\"inline\"\/><\/math> \u043a\u0430\u043a \u0441\u0442\u0435\u043f\u0435\u043d\u044c \u043f\u0440\u043e\u0441\u0442\u043e\u0433\u043e \u0447\u0438\u0441\u043b\u0430 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/112\/bb3\/965\/112bb396570b07f26f792e48c3447496.svg\" alt=\"$p$\" data-tex=\"inline\"\/><\/math> \u0432 \u043f\u0440\u0438\u043c\u0430\u0440\u043d\u043e\u043c \u0440\u0430\u0437\u043b\u043e\u0436\u0435\u043d\u0438\u0438 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/6d5\/92f\/b9f\/6d592fb9fbd278de0c91af9e724605da.svg\" alt=\"$n\\wr$\" data-tex=\"inline\"\/><\/math>. \u0422\u043e\u0433\u0434\u0430 \u0431\u0443\u0434\u0435\u0442 \u0441\u043f\u0440\u0430\u0432\u0435\u0434\u043b\u0438\u0432\u0430 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0430\u044f \u0444\u043e\u0440\u043c\u0443\u043b\u0430:  <\/p>\n<p><math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/df9\/215\/8f7\/df92158f767b38c9a2723e357cfff53f.svg\" alt=\"$l_p(n\\wr)=\\sum_{k\\geqslant1}\\lfloor\\frac{n}{p^k}\\rfloor\\:mod\\:2$\" data-tex=\"display\"\/><\/math><\/p>\n<p>  <\/p>\n<div class=\"spoiler\"><b class=\"spoiler_title\">\u0414\u043e\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044c\u0441\u0442\u0432\u043e<\/b><\/p>\n<div class=\"spoiler_text\">\u0412\u043e\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u043c\u0441\u044f <a href=\"https:\/\/en.wikipedia.org\/wiki\/Legendre%27s_formula\">\u0442\u0435\u043e\u0440\u0435\u043c\u043e\u0439 \u041b\u0435\u0436\u0430\u043d\u0434\u0440\u0430 \u043e \u043f\u0440\u043e\u0441\u0442\u044b\u0445 \u043c\u043d\u043e\u0436\u0438\u0442\u0435\u043b\u044f\u0445 \u0444\u0430\u043a\u0442\u043e\u0440\u0438\u0430\u043b\u0430<\/a>:  <\/p>\n<p><math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/826\/d04\/025\/826d04025d58f4367786c75dd7711950.svg\" alt=\"$\\begin{array}{ccl} l_p(n!\/\\lfloor n\/2\\rfloor!^2)&amp;=&amp;l_p(n!)-2l_p(\\lfloor n\/2\\rfloor!)\\\\ &amp;=&amp;\\sum_{k\\geqslant1}\\lfloor n\/p^k\\rfloor-2\\sum_{k\\geqslant1}\\lfloor \\lfloor n\/2\\rfloor\/p^k\\rfloor\\\\ &amp;=&amp;\\sum_{k\\geqslant1}(\\lfloor n\/p^k\\rfloor-2\\lfloor \\lfloor n\/p^k\\rfloor\/2\\rfloor) \\\\\\end{array}$\" data-tex=\"display\"\/><\/math><\/p>\n<p>  \u0414\u043b\u044f \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0435\u0433\u043e \u0432\u044b\u0440\u0430\u0436\u0435\u043d\u0438\u044f \u0432\u043e\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u043c\u0441\u044f \u0442\u0435\u043c \u0444\u0430\u043a\u0442\u043e\u043c, \u0447\u0442\u043e <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/031\/b3b\/985\/031b3b985b3d4ad1115e660471942f8a.svg\" alt=\"$j-2\\lfloor j\/2\\rfloor=j\\:mod\\:2$\" data-tex=\"inline\"\/><\/math>, \u0438 \u043f\u043e\u043b\u0443\u0447\u0438\u043c \u043d\u0443\u0436\u043d\u0443\u044e \u043d\u0430\u043c \u0444\u043e\u0440\u043c\u0443\u043b\u0443.  <\/div>\n<\/div>\n<p>  \u041a\u0430\u043a \u0441\u043b\u0435\u0434\u0441\u0442\u0432\u0438\u0435, <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/be8\/001\/c02\/be8001c02adc8bc8651f66b223a30922.svg\" alt=\"$l_p(n\\wr)\\leqslant log_p(n)$\" data-tex=\"inline\"\/><\/math> \u0438 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/4f9\/a82\/fe9\/4f9a82fe996071cba26cc8c81984f847.svg\" alt=\"$p^{l_p(n\\wr)}\\leqslant n$\" data-tex=\"inline\"\/><\/math>. \u0415\u0441\u043b\u0438 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/112\/bb3\/965\/112bb396570b07f26f792e48c3447496.svg\" alt=\"$p$\" data-tex=\"inline\"\/><\/math> \u043d\u0435\u0447\u0451\u0442\u043d\u043e, \u0442\u043e <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/b17\/e18\/841\/b17e18841fa2f00fd946a41d484743e2.svg\" alt=\"$l_p(p^a\\wr)=a$\" data-tex=\"inline\"\/><\/math>. \u0414\u0440\u0443\u0433\u0438\u0435 \u0447\u0430\u0441\u0442\u043d\u044b\u0435 \u0441\u043b\u0443\u0447\u0430\u0438:  <\/p>\n<p><math>$$display$$\\begin{array}{lrrl} (a)&#038;\\lfloor n\/2\\rfloor &#038;&lt; p \\leqslant &#038; n &#038; \\Rightarrow &#038; l_p(n\\wr)=1\\\\ (b)&#038;\\lfloor n\/3\\rfloor &#038;&lt; p \\leqslant &#038; \\lfloor n\/2\\rfloor &#038; \\Rightarrow &#038; l_p(n\\wr)=0\\\\ (c)&#038;\\sqrt{n} &#038;&lt; p \\leqslant &#038; \\lfloor n\/3\\rfloor &#038; \\Rightarrow &#038; l_p(n\\wr)=\\lfloor n\/p\\rfloor\\:mod\\:2\\\\ (d)&#038;2 &#038;&lt; p \\leqslant &#038; \\sqrt{n} &#038; \\Rightarrow &#038; l_p(n\\wr) &lt; log_2(n)\\\\ (e)&#038; &#038; p = &#038; 2 &#038; \\Rightarrow &#038; l_p(n\\wr) =\\sigma_2(\\lfloor n\/2\\rfloor)\\\\ \\end{array}$$display$$<\/math><\/p>\n<p>  <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/d7f\/8ac\/c89\/d7f8acc895764b95f679ac747a0d672b.svg\" alt=\"$\\sigma_2(n)$\" data-tex=\"inline\"\/><\/math> \u0437\u0434\u0435\u0441\u044c \u043e\u0437\u043d\u0430\u0447\u0430\u0435\u0442 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0435\u0434\u0438\u043d\u0438\u0446 \u0432 \u0434\u0432\u043e\u0438\u0447\u043d\u043e\u043c \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u0438 \u0447\u0438\u0441\u043b\u0430 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/17e\/d16\/be1\/17ed16be17023e4cd19584781c333593.svg\" alt=\"$n$\" data-tex=\"inline\"\/><\/math>. \u0412\u0441\u0435 \u044d\u0442\u0438 \u0444\u0430\u043a\u0442\u044b \u043c\u043e\u0433\u0443\u0442 \u0431\u044b\u0442\u044c \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u044b \u0434\u043b\u044f \u0434\u043e\u043f\u043e\u043b\u043d\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0439 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u0438 \u0432 \u043a\u043e\u0434\u0435. \u0414\u043e\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044c\u0441\u0442\u0432\u0430 \u044f \u043f\u0440\u0438\u0432\u043e\u0434\u0438\u0442\u044c \u043d\u0435 \u0431\u0443\u0434\u0443, \u043f\u0440\u0438 \u0436\u0435\u043b\u0430\u043d\u0438\u0438 \u0432\u044b \u043b\u0435\u0433\u043a\u043e \u0441\u043c\u043e\u0436\u0435\u0442\u0435 \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c \u0438\u0445 \u0441\u0430\u043c\u043e\u0441\u0442\u043e\u044f\u0442\u0435\u043b\u044c\u043d\u043e.<\/p>\n<p>  \u0422\u0435\u043f\u0435\u0440\u044c, \u0437\u043d\u0430\u044f \u0441\u0442\u0435\u043f\u0435\u043d\u0438 \u0432\u0441\u0435\u0445 \u043f\u0440\u043e\u0441\u0442\u044b\u0445 \u0434\u0435\u043b\u0438\u0442\u0435\u043b\u0435\u0439 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/6d5\/92f\/b9f\/6d592fb9fbd278de0c91af9e724605da.svg\" alt=\"$n\\wr$\" data-tex=\"inline\"\/><\/math>, \u0443 \u043d\u0430\u0441 \u0435\u0441\u0442\u044c \u0441\u043f\u043e\u0441\u043e\u0431 \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f <i>swinging factorial<\/i>:  <\/p>\n<p><math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/d9c\/621\/ae8\/d9c621ae8fff1eaa691bb3d05d3775a4.svg\" alt=\"$n\\wr=\\prod_{p\\leqslant n}p^{l_p(n\\wr)}$\" data-tex=\"display\"\/><\/math><\/p>\n<p>  <\/p>\n<h3>3. \u0422\u0440\u0443\u0434\u043e\u0451\u043c\u043a\u043e\u0441\u0442\u044c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430<\/h3>\n<p>  \u041c\u043e\u0436\u043d\u043e \u043f\u043e\u043a\u0430\u0437\u0430\u0442\u044c, \u0447\u0442\u043e \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u0435 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/6d5\/92f\/b9f\/6d592fb9fbd278de0c91af9e724605da.svg\" alt=\"$n\\wr$\" data-tex=\"inline\"\/><\/math> \u0438\u043c\u0435\u0435\u0442 \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/169\/ec0\/725\/169ec072596fac20efcc938cc5c8b3b6.svg\" alt=\"$O(n(log\\:n)^2log\\:log\\:n)$\" data-tex=\"inline\"\/><\/math>. \u041a\u0430\u043a \u043d\u0438 \u0441\u0442\u0440\u0430\u043d\u043d\u043e, \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u0435 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/490\/af1\/4ae\/490af14aea8ab65363cb21554c49e13b.svg\" alt=\"$n! $\" data-tex=\"inline\"\/><\/math> \u0438\u043c\u0435\u0435\u0442 \u0442\u0443 \u0436\u0435 \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c (\u0432 \u043e\u0446\u0435\u043d\u043a\u0435 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u0441\u044f <a href=\"https:\/\/ru.wikipedia.org\/wiki\/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D1%83%D0%BC%D0%BD%D0%BE%D0%B6%D0%B5%D0%BD%D0%B8%D1%8F_%D0%A8%D1%91%D0%BD%D1%85%D0%B0%D0%B3%D0%B5_%E2%80%94_%D0%A8%D1%82%D1%80%D0%B0%D1%81%D1%81%D0%B5%D0%BD%D0%B0\">\u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0428\u0451\u043d\u0445\u0430\u0433\u0435-\u0428\u0442\u0440\u0430\u0441\u0441\u0435\u043d\u0430<\/a>, \u043e\u0442\u0441\u044e\u0434\u0430 \u0438 \u0442\u0430\u043a\u0430\u044f \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u0430\u044f \u0442\u0440\u0443\u0434\u043e\u0451\u043c\u043a\u043e\u0441\u0442\u044c; \u0434\u043e\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044c\u0441\u0442\u0432\u0430 \u043f\u043e \u0441\u0441\u044b\u043b\u043a\u0435 \u0432 \u043a\u043e\u043d\u0446\u0435 \u0441\u0442\u0430\u0442\u044c\u0438). <\/p>\n<p>  \u041d\u0435\u0441\u043c\u043e\u0442\u0440\u044f \u043d\u0430 \u0442\u043e, \u0447\u0442\u043e \u0444\u043e\u0440\u043c\u0430\u043b\u044c\u043d\u043e \u043f\u0435\u0440\u0435\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u0435 \u0447\u0438\u0441\u0435\u043b \u043e\u0442 1 \u0434\u043e n \u0438\u043c\u0435\u0435\u0442 \u0442\u0443 \u0436\u0435 \u0442\u0440\u0443\u0434\u043e\u0451\u043c\u043a\u043e\u0441\u0442\u044c, \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c <i>PrimeSwing<\/i> \u043d\u0430 \u043f\u0440\u0430\u043a\u0442\u0438\u043a\u0435 \u043e\u043a\u0430\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u0441\u0430\u043c\u044b\u043c \u0431\u044b\u0441\u0442\u0440\u044b\u043c.<\/p>\n<h3>\u0421\u0441\u044b\u043b\u043a\u0438 \u0438 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f<\/h3>\n<p>  <\/p>\n<ul>\n<li><a href=\"http:\/\/www.luschny.de\/math\/factorial\/FastFactorialFunctions.htm\">\u0441\u0442\u0440\u0430\u043d\u0438\u0446\u0430 \u0441 \u0440\u0430\u0437\u043b\u0438\u0447\u043d\u044b\u043c\u0438 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430\u043c\u0438 \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f \u0444\u0430\u043a\u0442\u043e\u0440\u0438\u0430\u043b\u0430;<\/a><\/li>\n<li><a href=\"http:\/\/www.luschny.de\/math\/factorial\/SwingIntro.pdf\">\u0434\u0435\u0442\u0430\u043b\u044c\u043d\u043e\u0435 \u043e\u043f\u0438\u0441\u0430\u043d\u0438\u0435 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u0438\u0437 \u0441\u0442\u0430\u0442\u044c\u0438 (\u0438 \u043d\u0435 \u0442\u043e\u043b\u044c\u043a\u043e).<\/a><\/li>\n<\/ul>\n<p>  <\/p>\n<div class=\"spoiler\"><b class=\"spoiler_title\">\u0420\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f \u043d\u0430 Java<\/b><\/p>\n<div class=\"spoiler_text\">\n<pre><code class=\"java\">\/\/ main function public static BigInteger factorial(int n) {     return factorial(n, primes(n)); }  \/\/ recursive function with shared primes array private static BigInteger factorial(int n, int[] primes) {     if (n &lt; 2) return BigInteger.ONE;     BigInteger f = factorial(n \/ 2, primes);     BigInteger ps = primeSwing(n, primes);     return f.multiply(f).multiply(ps); }  \/\/ swinging factorial function private static BigInteger primeSwing(int n, int[] primes) {     List&lt;BigInteger&gt; multipliers = new ArrayList&lt;&gt;();     for (int i = 0; i &lt; primes.length && primes[i] &lt;= n; i++) {         int prime = primes[i];         BigInteger bigPrime = BigInteger.valueOf(prime);         BigInteger p = BigInteger.ONE;         int q = n;         while (q != 0) {             q = q \/ prime;             if (q % 2 == 1) {                 p = p.multiply(bigPrime);             }         }         if (!p.equals(BigInteger.ONE)) {             multipliers.add(p);         }     }     return product(multipliers, 0, multipliers.size() - 1); }  \/\/ fast product for the list of numbers private static BigInteger product(List&lt;BigInteger&gt; multipliers, int i, int j) {     if (i &gt; j) return BigInteger.ONE;     if (i == j) return multipliers.get(i);     int k = (i + j) &gt;&gt;&gt; 1;     return product(multipliers, i, k).multiply(product(multipliers, k + 1, j)); }  \/\/ Eratosthenes sieve private static int[] primes(int upTo) {     upTo++;     if (upTo &gt;= 0 && upTo &lt; 3) {         return new int[]{};     }      int length = upTo &gt;&gt;&gt; 1;     boolean sieve_bool[] = new boolean[length];     for (int i = 1, iterations = (int) Math.sqrt(length - 1); i &lt; iterations; i++) {         if (!sieve_bool[i]) {             for (int step = 2 * i + 1, j = i * (step + 1); j &lt; length; j += step) {                 sieve_bool[j] = true;             }         }     }      int not_primes = 0;     for (boolean not_prime : sieve_bool) {         if (not_prime) not_primes++;     }      int sieve_int[] = new int[length - not_primes];     sieve_int[0] = 2;     for (int i = 1, j = 1; i &lt; length; i++) {         if (!sieve_bool[i]) {             sieve_int[j++] = 2 * i + 1;         }     }      return sieve_int; } <\/code><\/pre>\n<p>  <\/div>\n<\/div>\n<p> \u0441\u0441\u044b\u043b\u043a\u0430 \u043d\u0430 \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b \u0441\u0442\u0430\u0442\u044c\u0438 <a href=\"https:\/\/habrahabr.ru\/post\/323770\/\"> https:\/\/habrahabr.ru\/post\/323770\/<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u041d\u0430\u0442\u043a\u043d\u0443\u0432\u0448\u0438\u0441\u044c \u043d\u0435\u0434\u0430\u0432\u043d\u043e \u043d\u0430 <a href=\"https:\/\/habrahabr.ru\/post\/327544\/\">\u044d\u0442\u0443 \u0441\u0442\u0430\u0442\u044c\u044e<\/a>, \u044f \u043f\u043e\u043d\u044f\u043b, \u0447\u0442\u043e \u0440\u0435\u0434\u043a\u043e \u0443\u043f\u043e\u043c\u0438\u043d\u0430\u044e\u0442\u0441\u044f \u0441\u043f\u043e\u0441\u043e\u0431\u044b \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f \u0444\u0430\u043a\u0442\u043e\u0440\u0438\u0430\u043b\u0430, \u043e\u0442\u043b\u0438\u0447\u043d\u044b\u0435 \u043e\u0442 \u0431\u0430\u043d\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u043f\u0435\u0440\u0435\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u044f \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u0445 \u0447\u0438\u0441\u0435\u043b. \u041d\u0443\u0436\u043d\u043e \u044d\u0442\u0443 \u0441\u0438\u0442\u0443\u0430\u0446\u0438\u044e \u0438\u0441\u043f\u0440\u0430\u0432\u0438\u0442\u044c.<br \/>  \u041f\u0440\u0435\u0434\u043b\u0430\u0433\u0430\u044e \u0440\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0435\u0442\u044c \u00ab\u0430\u0441\u0438\u043c\u043f\u0442\u043e\u0442\u0438\u0447\u0435\u0441\u043a\u0438 \u043d\u0430\u0438\u0431\u043e\u043b\u0435\u0435 \u0431\u044b\u0441\u0442\u0440\u044b\u0439\u00bb \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f \u0444\u0430\u043a\u0442\u043e\u0440\u0438\u0430\u043b\u0430!<\/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-285709","post","type-post","status-publish","format-standard","hentry"],"_links":{"self":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/285709","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=285709"}],"version-history":[{"count":0,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/285709\/revisions"}],"wp:attachment":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=285709"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=285709"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=285709"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}