{"id":781,"date":"2026-04-19T17:19:54","date_gmt":"2026-04-19T09:19:54","guid":{"rendered":"http:\/\/wordpress.fangt.online\/?p=781"},"modified":"2026-04-25T01:01:25","modified_gmt":"2026-04-24T17:01:25","slug":"%e7%b4%a0%e6%95%b0%e7%ad%9b-3-%e5%85%b3%e4%ba%8e%e6%ac%a7%e6%8b%89%e7%ad%9b%e7%9a%84%e6%8b%93%e5%b1%95%e7%94%a8%e6%b3%95","status":"publish","type":"post","link":"http:\/\/wordpress.fangt.online\/index.php\/2026\/04\/19\/%e7%b4%a0%e6%95%b0%e7%ad%9b-3-%e5%85%b3%e4%ba%8e%e6%ac%a7%e6%8b%89%e7%ad%9b%e7%9a%84%e6%8b%93%e5%b1%95%e7%94%a8%e6%b3%95\/","title":{"rendered":"\u7d20\u6570\u7b5b\uff1a\u6b27\u62c9\u7b5b\u7684\u66f4\u591a\u5e94\u7528"},"content":{"rendered":"\n<h2 class=\"wp-block-heading has-large-font-size\">1.\u8bb0\u5f55\u6700\u5c0f\u8d28\u56e0\u5b50<\/h2>\n\n\n\n<p class=\"has-medium-font-size wp-block-paragraph\">\u5728\u6b27\u62c9\u7b5b\u4e2d\uff0c\u6bcf\u4e2a\u5408\u6570\u88ab\u5b83\u7684\u6700\u5c0f\u8d28\u56e0\u5b50\u7b5b\u6389\u3002\u6211\u4eec\u53ef\u4ee5\u5229\u7528\u8fd9\u4e2a\u7279\u6027\uff0c\u5728\u7b5b\u7684\u8fc7\u7a0b\u4e2d\u8bb0\u5f55\u6bcf\u4e2a\u6570\u7684\u6700\u5c0f\u8d28\u56e0\u5b50 lp[x]\uff08least prime factor\uff09\u3002<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>void euler_sieve(int n) {\n    for (int i = 2; i &lt;= n; i++) {\n        if (!lp&#91;i]) {\n            lp&#91;i] = i;\n            primes.push_back(i);\n        }\n        for (int p : primes) {\n            if (p &gt; lp&#91;i] || i * p &gt; n) break;\n            lp&#91;i * p] = p;\n        }\n    }\n}<\/code><\/pre>\n\n\n\n<h2 class=\"wp-block-heading has-large-font-size\">2.\u5229\u7528\u6700\u5c0f\u8d28\u56e0\u5b50\u5206\u89e3\u8d28\u56e0\u6570<\/h2>\n\n\n\n<p class=\"has-medium-font-size wp-block-paragraph\">\u6709\u4e86&nbsp;<code>lp[x]<\/code>\uff0c\u6211\u4eec\u53ef\u4ee5<strong>\u5feb\u901f<\/strong>\uff08<math xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><semantics><mrow><mi>O<\/mi><mo stretchy=\"false\">(<\/mo><mi>log<\/mi><mo>\u2061<\/mo><mi>x<\/mi><mo stretchy=\"false\">)<\/mo><\/mrow><\/semantics><\/math>\uff09\u5206\u89e3\u4efb\u610f x \u7684\u8d28\u56e0\u6570\uff1a<\/p>\n\n\n\n<pre class=\"wp-block-code has-fira-code-font-family\"><code>vector&lt;pair&lt;int, int&gt;&gt; factorize(int x) {\n    vector&lt;pair&lt;int, int&gt;&gt; factors;\n    while (x &gt; 1) {\n        int p = lp&#91;x];\n        int cnt = 0;\n        while (x % p == 0) {\n            x \/= p;\n            cnt++;\n        }\n        factors.push_back({p, cnt});\n    }\n    return factors;\n}<\/code><\/pre>\n\n\n\n<p class=\"has-medium-font-size wp-block-paragraph\"><strong>\u65f6\u95f4\u590d\u6742\u5ea6<\/strong>\uff1a<math xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><semantics><mrow><mi>O<\/mi><mo stretchy=\"false\">(<\/mo><mtext>\u8d28\u56e0\u5b50\u4e2a\u6570<\/mtext><mo stretchy=\"false\">)<\/mo><\/mrow><\/semantics><\/math>\uff0c\u6700\u574f&nbsp;<math xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><semantics><mrow><mi>O<\/mi><mo stretchy=\"false\">(<\/mo><mi>log<\/mi><mo>\u2061<\/mo><mi>n<\/mi><mo stretchy=\"false\">)<\/mo><\/mrow><\/semantics><\/math>\uff08\u56e0\u4e3a\u6bcf\u6b21\u81f3\u5c11\u9664\u4ee5 2\uff09\u3002<\/p>\n","protected":false},"excerpt":{"rendered":"<p>1.\u8bb0\u5f55\u6700\u5c0f\u8d28\u56e0\u5b50 \u5728\u6b27\u62c9\u7b5b\u4e2d\uff0c\u6bcf\u4e2a\u5408\u6570\u88ab\u5b83\u7684\u6700\u5c0f\u8d28\u56e0\u5b50\u7b5b\u6389\u3002\u6211\u4eec\u53ef\u4ee5\u5229\u7528\u8fd9\u4e2a\u7279\u6027\uff0c\u5728\u7b5b\u7684\u8fc7\u7a0b\u4e2d\u8bb0\u5f55\u6bcf\u4e2a\u6570\u7684\u6700 [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[61],"tags":[],"class_list":["post-781","post","type-post","status-publish","format-standard","hentry","category-zl"],"_links":{"self":[{"href":"http:\/\/wordpress.fangt.online\/index.php\/wp-json\/wp\/v2\/posts\/781","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/wordpress.fangt.online\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/wordpress.fangt.online\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/wordpress.fangt.online\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/wordpress.fangt.online\/index.php\/wp-json\/wp\/v2\/comments?post=781"}],"version-history":[{"count":5,"href":"http:\/\/wordpress.fangt.online\/index.php\/wp-json\/wp\/v2\/posts\/781\/revisions"}],"predecessor-version":[{"id":890,"href":"http:\/\/wordpress.fangt.online\/index.php\/wp-json\/wp\/v2\/posts\/781\/revisions\/890"}],"wp:attachment":[{"href":"http:\/\/wordpress.fangt.online\/index.php\/wp-json\/wp\/v2\/media?parent=781"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/wordpress.fangt.online\/index.php\/wp-json\/wp\/v2\/categories?post=781"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/wordpress.fangt.online\/index.php\/wp-json\/wp\/v2\/tags?post=781"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}