{"id":1143,"date":"2015-07-01T21:23:09","date_gmt":"2015-07-01T13:23:09","guid":{"rendered":"http:\/\/www.shuizilong.com\/house\/?p=1143"},"modified":"2025-03-21T02:31:42","modified_gmt":"2025-03-20T18:31:42","slug":"project-euler-521-smallest-prime-factor","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/project-euler-521-smallest-prime-factor\/","title":{"rendered":"Project Euler 521. Smallest prime factor"},"content":{"rendered":"<p><!--more--><br \/>\n<a href=\"https:\/\/projecteuler.net\/problem=521\">https:\/\/projecteuler.net\/problem=521<\/a><\/p>\n<hr>\n<p>\u62c6\u89e3\u6210\u4e24\u4e2a\u5b50\u95ee\u9898\uff0c<\/p>\n<ul>\n<li>\u5c0f\u4e8e\u7b49\u4e8e n \u7684\u7d20\u6570\u4e4b\u548c\u3002<\/li>\n<li>\u5c0f\u4e8e\u7b49\u4e8e n \u7684\u5408\u6570\u7684\u6700\u5c0f\u7d20\u56e0\u5b50\u4e4b\u548c\u3002<\/li>\n<\/ul>\n<p>\u56de\u5fc6 PE 10\uff0c\u6211\u4eec\u53ef\u4ee5\u7528 $$O(n^{3\/4})$$ \u7684\u590d\u6742\u5ea6\u53bb\u7edf\u8ba1\u5c0f\u4e8e\u7b49\u4e8e n \u7684\u7d20\u6570\u7684 k \u6b21\u65b9\u548c\u3002<br \/>\n\u90a3\u4e48\u524d\u8005\u662f k=1\uff0c\u540e\u8005\u53ef\u4ee5\u6c42 k=0 \u7684\u65f6\u5019\u987a\u4fbf\u5f97\u5230\u3002\uff08\u56e0\u6b64\u6bcf\u6b21\u7b5b p \u8fc7\u7a0b\u4e2d\uff0cdp[n] \u7684\u53d8\u5316\uff0c\u5c31\u662f\u6240\u6709\u6700\u5c0f\u7d20\u56e0\u5b50\u7b49\u4e8e p \u7684\u5408\u6570\u7684\u4e2a\u6570\u3002\uff09<\/p>\n<pre class=\"brush: cpp; light: false; title: ; toolbar: true; notranslate\" title=\"\">\n\nInt f(LL n){\n    LL r = sqrt(n); vector&amp;lt;LL&amp;gt; V; REP_1(i, r+1) V.PB(n\/i);\n    int up = int(*V.rbegin()); DWN_1(i, up-1, 1) V.PB(i);\n\n&lt;pre&gt;&lt;code&gt;Int z = 0;\n\nunordered_map&amp;amp;lt;LL, LL&amp;amp;gt; dp;\n\nREP(i, V.size()){\n    LL x = V&#x5B;i];\n    dp&#x5B;x] = x-1;\n}\n\n\nFOR_1(p, 2, r+1) if (dp&#x5B;p] &amp;amp;gt; dp&#x5B;p-1]){\n    LL prev = dp&#x5B;n];\n    LL pp = (LL)p*p; for(auto v: V){\n        if (v &amp;amp;lt; pp) break;\n        dp&#x5B;v] -= (dp&#x5B;v\/p] - dp&#x5B;p-1]);\n    }\n    z += Int(p) * Int(prev - dp&#x5B;n]);\n}\nreturn z;\n&lt;\/code&gt;&lt;\/pre&gt;\n\n}\n\nInt g(LL n){\n    LL r = sqrt(n); vector&amp;lt;LL&amp;gt; V; REP_1(i, r+1) V.PB(n\/i);\n    int up = int(*V.rbegin()); DWN_1(i, up-1, 1) V.PB(i);\n\n&lt;pre&gt;&lt;code&gt;unordered_map&amp;amp;lt;LL, Int&amp;amp;gt; dp;\n\nREP(i, V.size()){\n    LL x = V&#x5B;i];\n    if (x&amp;amp;amp;1) dp&#x5B;x] = Int(x) * Int((x+1)\/2) - 1;\n    else dp&#x5B;x] = Int(x\/2) * Int(x+1) - 1;\n}\n\nFOR_1(p, 2, r+1) if (dp&#x5B;p] != dp&#x5B;p-1]) {\n    LL pp = (LL)p*p; for(auto v: V){\n        if (v &amp;amp;lt; pp) break;\n        dp&#x5B;v] -= Int(p)*(dp&#x5B;v\/p] - dp&#x5B;p-1]);\n    }\n}\nreturn dp&#x5B;n];\n&lt;\/code&gt;&lt;\/pre&gt;\n\n}\n\nint main(){\n\n#ifndef ONLINE_JUDGE\n    freopen(&amp;quot;\/users\/xiaodao\/desktop\/Exercise\/in.txt&amp;quot;, &amp;quot;r&amp;quot;, stdin);\n    \/\/freopen(&amp;quot;out.txt&amp;quot;, &amp;quot;w&amp;quot;, stdout);\n#endif\n\n&lt;pre&gt;&lt;code&gt;LL n = 1e12;\ncout &amp;amp;lt;&amp;amp;lt;  f(n)  + g(n) &amp;amp;lt;&amp;amp;lt; endl;\n\n\/\/44389811\n&lt;\/code&gt;&lt;\/pre&gt;\n\n}\n\n<\/pre>\n","protected":false},"excerpt":{"rendered":"","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","enabled":false}}},"categories":[143],"tags":[],"class_list":["post-1143","post","type-post","status-publish","format-standard","hentry","category-pe"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-ir","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1143","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/comments?post=1143"}],"version-history":[{"count":1,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1143\/revisions"}],"predecessor-version":[{"id":3421,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1143\/revisions\/3421"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=1143"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=1143"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=1143"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}