{"id":90,"date":"2013-01-17T21:20:17","date_gmt":"2013-01-18T05:20:17","guid":{"rendered":"http:\/\/willclausen.com\/?p=90"},"modified":"2013-01-17T21:24:49","modified_gmt":"2013-01-18T05:24:49","slug":"solution-project-euler-problem-3","status":"publish","type":"post","link":"http:\/\/willclausen.com\/?p=90","title":{"rendered":"Solution: Project Euler Problem 3"},"content":{"rendered":"<p>The Problem:<\/p>\n<p style=\"padding-left: 30px;\">What is the largest prime factor of the number 600851475143 ?<\/p>\n<p>My solution (in C++):<\/p>\n<pre class=\"brush: cpp; light: false; title: ; toolbar: true; notranslate\" title=\"\">\r\n\r\n\/\/ Author: Will Clausen\r\n\/\/\r\n\/\/ Date: Jan 6, 2013\r\n\/\/\r\n\/\/ This program will solve problem 3 of Project Euler\r\n\r\n#include\r\n#include\r\n#include\r\n#include\r\n\r\nusing namespace std;\r\n\r\n\/\/ This function returns the largest prime factor of a\r\n\/\/ number given as an argument\r\nsize_t largestPrime(size_t Num)\r\n{\r\n\tsize_t remaining = Num;\r\n\tset&lt;size_t&gt; primes;\r\n\r\n\t\/\/ Handle the case where the number is even\r\n\tif (remaining % 2 == 0) {\r\n\t\tprimes.insert(2);\r\n\t}\r\n\r\n\twhile (remaining % 2 == 0) {\r\n\t\tremaining \/= 2;\r\n\t}\r\n\r\n\t\/\/ This is going to be an unorthodox for-loop\r\n\t\/\/ where the rhs of the comparison step is\r\n\t\/\/ modified within the loop.\r\n\tfor (size_t i = 3; i &lt;= size_t(sqrt(remaining)); i += 2) {\r\n\t\tif (remaining % i == 0) {\r\n\t\t\tcout &lt;&lt; &quot;The prime is: &quot; &lt;&lt; i &lt;&lt; endl;\r\n\t\t\tremaining = remaining\/i;\r\n\t\t\tcout &lt;&lt; &quot;Now the number remaining is: &quot; &lt;&lt; remaining &lt;&lt; endl; \t\t\tprimes.insert(i); \t\t\ti = 3; \t\t} \t} \t\/\/ The number itself might be prime, so check that case. \tif (remaining &gt; 3) {\r\n\t\tprimes.insert(remaining);\r\n\t}\r\n\r\n\t\/\/ Loop throught the set and find the largest prime.\r\n\tsize_t maxPrime = 1;\r\n\tfor (set&lt;size_t&gt;::iterator it = primes.begin(); it != primes.end(); ++it) {\r\n\t\tif (*it &gt; maxPrime) {\r\n\t\t\tmaxPrime = *it;\r\n\t\t}\r\n\t}\r\n\r\n\treturn maxPrime;\r\n}\r\n\r\n\/\/ Solution: 6857\r\n\r\n<\/pre>\n<p>This may be faster if I pre-generate primes less than the input using the Sieve of Eratosthenes method, then dividing by those primes.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>The Problem: What is the largest prime factor of the number 600851475143 ? My solution (in C++): \/\/ Author: Will Clausen \/\/ \/\/ Date: Jan 6, 2013 \/\/ \/\/ This program will solve problem 3 of Project Euler #include #include #include #include using namespace std; \/\/ This function returns the largest prime factor of a [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[18],"tags":[9,22,19],"class_list":["post-90","post","type-post","status-publish","format-standard","hentry","category-project-euler-solutions","tag-january2013","tag-project-euler-problem-3","tag-project-euler-solution"],"_links":{"self":[{"href":"http:\/\/willclausen.com\/index.php?rest_route=\/wp\/v2\/posts\/90","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/willclausen.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/willclausen.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/willclausen.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/willclausen.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=90"}],"version-history":[{"count":4,"href":"http:\/\/willclausen.com\/index.php?rest_route=\/wp\/v2\/posts\/90\/revisions"}],"predecessor-version":[{"id":93,"href":"http:\/\/willclausen.com\/index.php?rest_route=\/wp\/v2\/posts\/90\/revisions\/93"}],"wp:attachment":[{"href":"http:\/\/willclausen.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=90"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/willclausen.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=90"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/willclausen.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=90"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}