{"id":96,"date":"2012-03-15T17:33:19","date_gmt":"2012-03-15T09:33:19","guid":{"rendered":"http:\/\/www.freezhongzi.info\/?p=96"},"modified":"2019-03-26T15:38:42","modified_gmt":"2019-03-26T07:38:42","slug":"%e6%89%be%e8%b4%a8%e6%95%b0%e7%ae%97%e6%b3%95%e4%b9%8b%e5%9f%83%e6%8b%89%e6%89%98%e6%96%af%e7%89%b9%e5%b0%bc%e7%ad%9b%e6%b3%95sieve-of-eratosthenes","status":"publish","type":"post","link":"https:\/\/bl4kraven.com\/index.php\/2012\/03\/15\/%e6%89%be%e8%b4%a8%e6%95%b0%e7%ae%97%e6%b3%95%e4%b9%8b%e5%9f%83%e6%8b%89%e6%89%98%e6%96%af%e7%89%b9%e5%b0%bc%e7%ad%9b%e6%b3%95sieve-of-eratosthenes\/","title":{"rendered":"\u627e\u8d28\u6570\u7b97\u6cd5\u4e4b\u57c3\u62c9\u6258\u65af\u7279\u5c3c\u7b5b\u6cd5(Sieve of Eratosthenes)"},"content":{"rendered":"

\u4ee5\u524d\u6211\u5728Project Euler<\/a>\u4e0a\u505a\u9898\u65f6\u5f88\u591a\u90fd\u662f\u8ddf\u8d28\u6570\u6709\u5173\u7684\uff0c\u800c\u6258\u65af\u7279\u5c3c\u7b5b\u6cd5(Sieve of Eratosthenes)<\/a>\u662f\u6211\u611f\u89c9\u6700\u7b80\u6d01\u5f3a\u5927\u7684\uff0c\u5b83\u7684\u7b97\u6cd5\u590d\u6742\u5ea6\u8981\u5c0f\u4e8eO(n)\uff0c\u5178\u578b\u7684\u7a7a\u95f4\u6362\u65f6\u95f4\u7b97\u6cd5\u3002<\/p>\n

 <\/p>\n

\"\u57c3\u62c9\u6258\u65af\u7279\u5c3c\u7b5b\u6cd5\"<\/center> <\/p>\n

\u6309\u6211\u7684\u7406\u89e3\u4e0d\u540c\u4e8e\u5176\u4ed6\u7528\u5faa\u73af\u8bd5\u9664\u67e5\u627e\u8d28\u6570\u7684\u65b9\u6cd5\uff0c\u57c3\u62c9\u6258\u65af\u7279\u5c3c\u7b5b\u6cd5\u4e0d\u7528\u9664\u6cd5\u800c\u662f\u7528\u4e58\u6cd5\u3002\u539f\u7406\u5f88\u7b80\u5355\uff1a<\/p>\n

    \n
  1. \u5047\u8bbe\u6709\u5f20\u8868\u91cc\u9762\u653e\u4e86\u6570\u5b572\u523010<\/li>\n
  2. \u56e0\u4e3a2\u7684\u500d\u6570\uff1a4\u30016\uff0c8\uff0c10\u90fd\u662f\u5408\u6570\uff0c\u6240\u4ee5\u7528\u7b14\u5212\u6389\uff0c\u5269\u4e0b3\u30015\u30017\u30019\uff0c\u800c\u7b2c\u4e00\u4e2a\u6ca1\u6709\u88ab\u5212\u6389\u7684\u662f\u8d28\u6570\uff0c\u6240\u4ee53\u662f\u8d28\u6570\uff08\u56e0\u4e3a3\u4e0d\u662f\u5c0f\u4e8e3\u7684\u6570\u7684\u500d\u6570\uff0c\u4e5f\u5c31\u662f\u8bf4\u4e0d\u80fd\u88ab\u6574\u9664\uff09\u3002<\/li>\n
  3. \u5212\u53bb3\u7684\u500d\u6570\uff1a9\uff0c\u5269\u4e0b5\u30017\uff0c\u6240\u4ee55\u662f\u8d28\u6570<\/li>\n
  4. \u5212\u53bb5\u7684\u500d\u6570\uff1a\u65e0\uff0c\u5269\u4e0b7\uff0c\u6240\u4ee57\u662f\u8d28\u6570<\/li>\n
  5. \u5212\u53bb7\u7684\u500d\u6570\uff1a\u65e0\uff0c\u6ca1\u6709\u5269\u4e0b\u6570\u5b57<\/li>\n
  6. \u67e5\u627e\u5b8c\u6bd5\uff0c\u8d28\u6570\u662f(2\u30013\u30015\u30017)<\/li>\n<\/ol>\n

    \u8fd9\u4e2a\u64cd\u4f5c\u5f88\u50cf\u7b5b\u6c99\u5b50\uff0c\u6240\u4ee5\u7b5b\u6cd5\u56e0\u6b64\u5f97\u540d\u5427\uff0c\u8fd9\u91cc\u6709\u4e00\u4e2a\u5728\u7ebfJavaScript\u6f14\u793a\u7248<\/a>\u3002\u5982\u679c\u8fd9\u5f20\u8868\u957f\u4e3aN\uff0c\u4e00\u822c\u53ea\u8981\u5212\u53bb\u5c0f\u4e8e\u7b49\u4e8eN\u5e73\u65b9\u6839\u7684\u6570\u7684\u500d\u6570<\/strong>\u5c31\u53ef\u4ee5\u4e86\uff0c\u56e0\u4e3a\u5c0f\u4e8eN\u7684\u6570\u5982\u679c\u4e3a\u5408\u6570\u4e00\u5b9a\u6709\u4e00\u4e2a\u5c0f\u4e8e\u7b49\u4e8eN\u5e73\u65b9\u6839\u7684\u8d28\u6570\uff0c\u800c\u65e2\u7136\u6211\u4eec\u5df2\u7ecf\u5212\u5230\u4e86N\u7684\u5e73\u65b9\u6839\u4e86\uff0c\u6240\u4ee5\u5269\u4e0b\u7684\u90fd\u662f\u8d28\u6570\u5566\u3002<\/p>\n

    \u5177\u4f53\u67e5\u627e\u8d28\u6570\u7684\u7f16\u7a0b\u6b65\u9aa4\uff1a<\/p>\n

      \n
    1. \u5efa\u7acb\u4ece2\u5230N\u7684\u8868<\/li>\n
    2. \u627e\u5230\u7b2c\u4e00\u4e2a\u6ca1\u6709\u5212\u6389\u7684\u6570p\uff0c\u8fd9\u662f\u4e2a\u8d28\u6570\u3002\u5982\u679cp\u5927\u4e8eN\u7684\u5e73\u65b9\u6839\uff0c\u8df3\u5230\u6b65\u9aa45<\/li>\n
    3. \u5212\u6389\u6240\u6709\u6ca1\u6709\u5212\u6389\u7684p\u7684\u500d\u4e58<\/li>\n
    4. \u8df3\u5230\u6b65\u9aa42<\/li>\n
    5. \u6ca1\u6709\u88ab\u5212\u6389\u7684\u90fd\u662f\u5c0f\u4e8e\u7b49\u4e8eN\u7684\u8d28\u6570<\/li>\n<\/ol>\n

      \u4e0a\u4e2aPython\u4ee3\u7801\uff0c\u67e5\u627e\u5c0f\u4e8e\u7b49\u4e8e65536\u7684\u8d28\u6570:<\/p>\n

      # -*- coding:UTF-8 -*-\nimport math\n\ndef main():\n    # \u8d28\u6570\u7b5b\u5b50\uff0c\u5c0f\u4e8e\u7b49\u4e8e65536\u7684\u8d28\u6570\n    size = 65536\n    limit = int(math.sqrt(size))\n    # \u591a\u52a0\u4e00\u4e2a\uff0c\u65b9\u4fbf\u7d22\u5f15\u4ece0\u5f00\u59cb\n    sieve = [True] * (size + 1)\n\n    prime = []\n    for index in range(2, limit + 1):\n        if sieve[index] == True:\n            # \u7b2c\u4e00\u4e2a\u6ca1\u88ab\u5212\u6389\u7684\u662f\u8d28\u6570\n            prime.append(index)\n\n            # \u5212\u6389index\u7684\u500d\u4e58\n            for factor in range(index*2, size+1, index):\n                sieve[factor] = False\n\n    # \u5269\u4e0b\u7684\u90fd\u662f\u8d28\u6570\n    for index in range(limit + 1, size+1):\n        if sieve[index] == True:\n            prime.append(index)\n\n    # \u663e\u793a\u6240\u4ee5\u8d28\u6570\n    print prime\n\nif __name__ == \"__main__\":\n    main()\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
      \u4ee5\u524d\u6211\u5728Project Euler\u4e0a\u505a\u9898\u65f6\u5f88\u591a\u90fd\u662f\u8ddf\u8d28\u6570\u6709\u5173\u7684\uff0c\u800c\u6258\u65af\u7279\u5c3c\u7b5b\u6cd5( … \u7ee7\u7eed\u9605\u8bfb →<\/span><\/a> \u7ee7\u7eed\u9605\u8bfb →<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[5],"tags":[],"class_list":["post-96","post","type-post","status-publish","format-standard","hentry","category-program"],"_links":{"self":[{"href":"https:\/\/bl4kraven.com\/index.php\/wp-json\/wp\/v2\/posts\/96","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/bl4kraven.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/bl4kraven.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/bl4kraven.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/bl4kraven.com\/index.php\/wp-json\/wp\/v2\/comments?post=96"}],"version-history":[{"count":2,"href":"https:\/\/bl4kraven.com\/index.php\/wp-json\/wp\/v2\/posts\/96\/revisions"}],"predecessor-version":[{"id":507,"href":"https:\/\/bl4kraven.com\/index.php\/wp-json\/wp\/v2\/posts\/96\/revisions\/507"}],"wp:attachment":[{"href":"https:\/\/bl4kraven.com\/index.php\/wp-json\/wp\/v2\/media?parent=96"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/bl4kraven.com\/index.php\/wp-json\/wp\/v2\/categories?post=96"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/bl4kraven.com\/index.php\/wp-json\/wp\/v2\/tags?post=96"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}