The problem is to find the largest prime factor of 600851475143.<\/p>\n
Some ugly python and an ugly solution. Clearly not very computationally efficient as I’m recalculating primes each time. There are also other computationally more efficient solutions out there in any case. This is just here for my reference:<\/p>\n
\r\nimport math\r\n\r\ndef getprimes(input):\r\n i = input #math.sqrt(input)\r\n\r\n vals = range(2,int(i))\r\n\r\n for n in vals:\r\n for j in xrange(n+n,int(i),n):\r\n if j in vals:\r\n vals.remove(j)\r\n\r\n vals.reverse()\r\n return vals\r\n\r\ninput = 600851475143L\r\n\r\nprimes_max = 100\r\n\r\nwhile 1:\r\n primes = getprimes(primes_max)\r\n #print primes\r\n p = 0\r\n for i in primes:\r\n if input%i == 0:\r\n print "factor: ",i\r\n input = input\/i\r\n p = 1\r\n\r\n\r\n if primes_max > math.sqrt(input):\r\n if p == 0:\r\n print "factor: ",input\r\n break\r\n\r\n primes_max = primes_max + 1000\r\n print primes_max\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"The problem is to find the largest prime factor of 600851475143. Some ugly python and an ugly solution. Clearly not very computationally efficient as I’m recalculating primes each time. There are also other computationally more efficient solutions out there in any case. This is just here for my reference: import math def getprimes(input): i = […]<\/p>\n","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","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[1],"tags":[],"class_list":["post-746","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p1RRoU-c2","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/posts\/746","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/comments?post=746"}],"version-history":[{"count":1,"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/posts\/746\/revisions"}],"predecessor-version":[{"id":747,"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/posts\/746\/revisions\/747"}],"wp:attachment":[{"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/media?parent=746"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/categories?post=746"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/tags?post=746"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}