{"id":1498,"date":"2020-08-31T23:13:31","date_gmt":"2020-09-01T06:13:31","guid":{"rendered":"http:\/\/209.126.2.187\/?p=1498"},"modified":"2020-10-18T20:57:45","modified_gmt":"2020-10-19T03:57:45","slug":"prime-numbers","status":"publish","type":"post","link":"https:\/\/nanzhou.cc\/index.php\/2020\/08\/31\/prime-numbers\/","title":{"rendered":"Prime Numbers"},"content":{"rendered":"\n<h2 class=\"wp-block-heading\">Prime Numbers in [1, n]<\/h2>\n\n\n\n<p>The naive method takes O(n^1.5)) time.<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code class=\"\">\/\/ O(sqrt(a))\nbool IsPrime(a) {\n  if (a &lt; 2) return false;\n  for (int i = 2; i * i &lt;= a; ++i) {\n    if (a % i == 0) {\n      return false;\n    }\n  }\n  return true;\n}\n\nvector&lt;int> primes;\n\/\/ use long long to avoid that i*i overflows\nfor (long long i = 2; i &lt;= n; ++i) {\n    if (IsPrime[i]) {\n        primes.push_back(i);\n    }\n}<\/code><\/pre>\n\n\n\n<p>We could use the famous <a href=\"https:\/\/en.wikipedia.org\/wiki\/Sieve_of_Eratosthenes\">Sieve of Eratosthenes<\/a> algorithm.<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code lang=\"cpp\" class=\"language-cpp\">vector&lt;int> primes;\nvector&lt;bool> is_prime(n, true);\n\/\/ O(nloglogn)\n\/\/ https:\/\/oi-wiki.org\/math\/sieve\/\n\/\/ use long long to avoid that i*i overflows\nfor (long long i = 2; i &lt;= n; ++i) {\n    if (is_prime[i]) {\n        primes.push_back(i);\n        for (long long j = i * i; j &lt;= n; j += i) {\n            is_prime[j] = false;\n        }\n    }\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Prime Numbers in [1, n] The naive method takes O(n^1.5)) time. We could use the famous Sieve of Eratosthenes algorithm.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[48,49],"tags":[],"class_list":["post-1498","post","type-post","status-publish","format-standard","hentry","category-alg","category-math"],"_links":{"self":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/1498","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/comments?post=1498"}],"version-history":[{"count":5,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/1498\/revisions"}],"predecessor-version":[{"id":1518,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/1498\/revisions\/1518"}],"wp:attachment":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/media?parent=1498"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/categories?post=1498"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/tags?post=1498"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}