There are a number of sieve algorithms that can be used to list\u00c2\u00a0prime numbers up to a certain value. \u00c2\u00a0I came up with this implementation\u00c2\u00a0in Scala. I rather like it, as it makes no use of division, modulus, and only one (explicit) multiplication.<\/p>\n
Despite being in Scala, it’s not in a functional style. It uses the awesome\u00c2\u00a0mutable BitSet data structure which is very efficient in space and time. It is intrinsically ordered and it allows an iterator, which makes jumping to the next known prime easy. Constructing a BitSet from a for comprehension is also easy with breakOut.<\/p>\n
The basic approach is the start with a large BitSet filled will all odd numbers (and 2), then iterate through the BitSet, constructing a new BitSet containing numbers to be crossed off, which is easily done with the &~= (and-not) reassignment method. Since this is a logical bitwise operation, it’s blazing fast. This code takes longer to compile than run\u00c2\u00a0on my oldish MacBook Air.<\/p>\n
\r\nimport scala.collection.mutable.BitSet\r\nimport scala.collection.breakOut<\/pre>\nprintln(new java.util.Date())\r\nval top = 200000<\/pre>\nval sieve = BitSet(2)\r\nsieve |= (3 to top by 2).map(identity)(breakOut)<\/pre>\nval iter = sieve.iteratorFrom(3)\r\nwhile(iter.hasNext) {\r\n val n = iter.next\r\n sieve &~= (2*n to top by n).map(identity)(breakOut)\r\n}<\/pre>\nprintln(sieve.toIndexedSeq(10000)) \/\/ 0-based\r\nprintln(new java.util.Date())<\/pre>\nAs written here, it’s a solution to Euler #7<\/a>, but it could be made even faster for more general use.<\/p>\n
For example<\/p>\n