{"action":"created","issue":{"url":"https://api.github.com/repos/JuliaLang/julia/issues/12025","labels_url":"https://api.github.com/repos/JuliaLang/julia/issues/12025/labels{/name}","comments_url":"https://api.github.com/repos/JuliaLang/julia/issues/12025/comments","events_url":"https://api.github.com/repos/JuliaLang/julia/issues/12025/events","html_url":"https://github.com/JuliaLang/julia/pull/12025","id":93198196,"number":12025,"title":"Improve prime sieve performance","user":{"login":"pabloferz","id":8410335,"avatar_url":"https://avatars.githubusercontent.com/u/8410335?v=3","gravatar_id":"","url":"https://api.github.com/users/pabloferz","html_url":"https://github.com/pabloferz","followers_url":"https://api.github.com/users/pabloferz/followers","following_url":"https://api.github.com/users/pabloferz/following{/other_user}","gists_url":"https://api.github.com/users/pabloferz/gists{/gist_id}","starred_url":"https://api.github.com/users/pabloferz/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/pabloferz/subscriptions","organizations_url":"https://api.github.com/users/pabloferz/orgs","repos_url":"https://api.github.com/users/pabloferz/repos","events_url":"https://api.github.com/users/pabloferz/events{/privacy}","received_events_url":"https://api.github.com/users/pabloferz/received_events","type":"User","site_admin":false},"labels":[{"url":"https://api.github.com/repos/JuliaLang/julia/labels/performance","name":"performance","color":"d7e102"}],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":26,"created_at":"2015-07-06T06:03:02Z","updated_at":"2015-08-07T11:21:49Z","closed_at":null,"pull_request":{"url":"https://api.github.com/repos/JuliaLang/julia/pulls/12025","html_url":"https://github.com/JuliaLang/julia/pull/12025","diff_url":"https://github.com/JuliaLang/julia/pull/12025.diff","patch_url":"https://github.com/JuliaLang/julia/pull/12025.patch"},"body":"This PR changes the algorithm used in `primesmask` from a Sieve of Atkin to a Sieve of Eratosthenes, based on the ~~idea~~ redesign proposed by @VicDrastik in #11594.\r\n\r\nThe main ideas used are\r\n\r\n* ~~Most integers are composite, so it is better to set all flags to false initially, then invert for possible primes~~\r\n* ~~Except for 2, 3 all primes are of the from 6k ± 1~~\r\n* Implement a 30 wheel sieve. This sieve stores a flag for each number of the form 30k + p where p is one of `[7, 11, 13, 17, 19, 23, 29, 31]` (all primes greater than 5 are of this form).\r\n* Cross-off multiples of p of the above form, starting from p².\r\n* Use the wheel sieve `_primesmask` (not exported) to construct `primesmask` and to find primes.\r\n\r\nAdditionally, the function `primesmask` is now exported and both this function and `primes` are extended in order to generate all the primes between two integers.\r\n\r\nAs a follow-up, it would be worth trying to write a general segmented version (perhaps a mix between this and the ideas of @ironman353 in #11594 or this http://primesieve.org/segmented_sieve.html).\r\n\r\nI apologize to @Ismael-VC who was also working on this in #11927 (his approach was to fix the current implementation of the Sieve of Atkin, but this should be even faster as suggested in #11594).\r\n\r\nFinally, this PR addresses the initial issue on #11594 but that turned out to be a discussion on how to improve the whole support for primes. Maybe that one should be separated into smaller issues and grouped into a master issue.\r\n\r\nCC @danaj @aiorla @StefanKarpinski "},"comment":{"url":"https://api.github.com/repos/JuliaLang/julia/issues/comments/128678472","html_url":"https://github.com/JuliaLang/julia/pull/12025#issuecomment-128678472","issue_url":"https://api.github.com/repos/JuliaLang/julia/issues/12025","id":128678472,"user":{"login":"tkelman","id":5934628,"avatar_url":"https://avatars.githubusercontent.com/u/5934628?v=3","gravatar_id":"","url":"https://api.github.com/users/tkelman","html_url":"https://github.com/tkelman","followers_url":"https://api.github.com/users/tkelman/followers","following_url":"https://api.github.com/users/tkelman/following{/other_user}","gists_url":"https://api.github.com/users/tkelman/gists{/gist_id}","starred_url":"https://api.github.com/users/tkelman/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/tkelman/subscriptions","organizations_url":"https://api.github.com/users/tkelman/orgs","repos_url":"https://api.github.com/users/tkelman/repos","events_url":"https://api.github.com/users/tkelman/events{/privacy}","received_events_url":"https://api.github.com/users/tkelman/received_events","type":"User","site_admin":false},"created_at":"2015-08-07T11:21:49Z","updated_at":"2015-08-07T11:21:49Z","body":"Is `primesmask` ending up in the generated RST docs? If not, I think you need to add a signature for it so `doc/genstdlib.jl` can fill in the docstring."}}