{"id":1643,"date":"2009-08-26T12:34:54","date_gmt":"2009-08-26T11:34:54","guid":{"rendered":"http:\/\/www.walkingrandomly.com\/?p=1643"},"modified":"2009-08-27T11:18:15","modified_gmt":"2009-08-27T10:18:15","slug":"finding-prime-numbers-using-voodoo-regular-expressions","status":"publish","type":"post","link":"https:\/\/walkingrandomly.com\/?p=1643","title":{"rendered":"Finding prime numbers using <del>voodoo<\/del> regular expressions"},"content":{"rendered":"<p>If you have learned how to program then the odds are that you have written a program that displays a list of prime numbers.\u00a0 A prime number generator is a programming rite of passage that is almost up there with the ubiquitous &#8216;<a href=\"http:\/\/en.wikipedia.org\/wiki\/Hello_world_program\">Hello World<\/a>&#8216; application (for programmers who are going on to do numerical work at least).<\/p>\n<p>There are various ways you might choose to do it but I bet that your first (or even your second or third) thought wouldn&#8217;t be &#8216;<em>I know &#8211; I&#8217;ll use a <a href=\"http:\/\/en.wikipedia.org\/wiki\/Regular_expression\">regular expression<\/a>&#8216;.<\/em> Someone known only as &#8216;Abigail&#8217; obviously thought that the world desperately needed such a regex since he \/ she came up with the following incantation<\/p>\n<pre>^1?$|^(11+?)\\1+$<\/pre>\n<p>Which is a regular expression that I assure you can be used to generate a list of all the prime numbers.\u00a0 If you are in the mood for a puzzle then sit back, grab a cup of coffee and try to work out HOW it can generate the primes.<\/p>\n<p>If you give up then head over to <a href=\"http:\/\/www.pythonprogramminglanguage.info\/2009\/08\/25\/the-story-of-the-regexp-and-the-primes\/\">Python Programming<\/a> for a full explanation along with Python code that demonstrates that it really does work.<\/p>\n<p>Can anyone come up with regular expressions for other interesting series of numbers?<\/p>\n<p><strong>Update (27th August 2009): <\/strong>Someone pointed me to <a href=\"http:\/\/www.noulakaz.net\/weblog\/2007\/03\/18\/a-regular-expression-to-check-for-prime-numbers\/\">an alternative explanation here<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>If you have learned how to program then the odds are that you have written a program that displays a list of prime numbers.\u00a0 A prime number generator is a programming rite of passage that is almost up there with the ubiquitous &#8216;Hello World&#8216; application (for programmers who are going on to do numerical work [&hellip;]<\/p>\n","protected":false},"author":3,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":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":[6,7,31],"tags":[],"class_list":["post-1643","post","type-post","status-publish","format-standard","hentry","category-general-math","category-programming","category-python"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p3swhs-qv","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/walkingrandomly.com\/index.php?rest_route=\/wp\/v2\/posts\/1643","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/walkingrandomly.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/walkingrandomly.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/walkingrandomly.com\/index.php?rest_route=\/wp\/v2\/users\/3"}],"replies":[{"embeddable":true,"href":"https:\/\/walkingrandomly.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1643"}],"version-history":[{"count":8,"href":"https:\/\/walkingrandomly.com\/index.php?rest_route=\/wp\/v2\/posts\/1643\/revisions"}],"predecessor-version":[{"id":1652,"href":"https:\/\/walkingrandomly.com\/index.php?rest_route=\/wp\/v2\/posts\/1643\/revisions\/1652"}],"wp:attachment":[{"href":"https:\/\/walkingrandomly.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1643"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/walkingrandomly.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1643"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/walkingrandomly.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1643"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}