{"id":1512,"date":"2020-09-18T22:00:03","date_gmt":"2020-09-19T05:00:03","guid":{"rendered":"http:\/\/209.126.2.187\/?p=1512"},"modified":"2020-10-18T22:00:32","modified_gmt":"2020-10-19T05:00:32","slug":"prime-factorization","status":"publish","type":"post","link":"https:\/\/nanzhou.cc\/index.php\/2020\/09\/18\/prime-factorization\/","title":{"rendered":"Prime Factorization"},"content":{"rendered":"\n<p>The <a href=\"http:\/\/161.97.122.139\/index.php\/2020\/08\/31\/prime-numbers\/\">this post<\/a>, we introduced how to get all prime numbers from <code>1<\/code> to <code>n<\/code> in <code>o(nloglogn)<\/code> time. Base on which, we can do prime factorization in <code>O(logn) <\/code>time. <\/p>\n\n\n\n<pre class=\"wp-block-code\"><code lang=\"cpp\" class=\"language-cpp line-numbers\">constexpr int kMaxNum = 100001;\n\/\/ Finds all prime numbers in [2, kMaxNum];\n\/\/ Finds the smallest prime factor for any number\nint num_to_smallest_prime_factor[kMaxNum + 1]\n\/\/ O(nloglogn)\nvoid FindParimes() {\n    bool is_prime[kMaxNum + 1];\n    memset(is_prime, 1, sizeof(is_prime));\n    memset(num_to_smallest_prime_factor, 0, sizeof(num_to_smallest_prime_factor));\n    for (int i = 2; i &lt;= kMaxNum; ++i) {\n        if (!is_prime[i]) {\n            continue;\n        }\n        num_to_smallest_prime_factor[i] = i;\n        for (long long j = (long long)i * i; j &lt;= kMaxNum; j += i) {\n            if (num_to_smallest_prime_factor[j] == 0) {\n                num_to_smallest_prime_factor[j] = i;\n            }\n            is_prime[j] = false;\n        }\n    }\n}\n\n\/\/ Returns all prime factors of num\n\/\/ O(logn) since num is divided by at least 2 each time \nvector&lt;int> PrimeFactorization(int num) {\n    vector&lt;int> res;\n    while (num > 1) {\n        int prime = num_to_smallest_prime_factor[num];\n        res.push_back(prime);\n        while (num % prime == 0) {\n            num \/= prime;\n        }\n    }\n    return res;\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>The this post, we introduced how to get all prime numbers from 1 to n in o(nloglogn) time. Base on which, we can do prime factorization in O(logn) time.<\/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-1512","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\/1512","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=1512"}],"version-history":[{"count":1,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/1512\/revisions"}],"predecessor-version":[{"id":1519,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/1512\/revisions\/1519"}],"wp:attachment":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/media?parent=1512"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/categories?post=1512"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/tags?post=1512"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}