CODEWITHSUNDEEP
groovy
Ant's
Ant's

Reputation: 13811

What does this Groovy code actually do?

After following this link prime number in Groovy I came to see across the bit of code(in the comments) as :

​def t = (0..10000).flatten()
t[0]=0; t[1]=0; // 0 and 1 are not prime
def L = Math.sqrt(t.size()-1)
( [2,(3..L).step(2)].flatten()).each { n ->
  if(t[n]) {
    def delta = n==2?1:2;
    (((n*n)..(t.size())).step(n*delta)).each {
      i -> t[i] = 0
    }
  }
}
println t.findAll({ it != 0 })

What is special about this code is that it is faster. I run this snippet to find prime for one billion, and it does the job in less than one min. But at the same time couldn't figure out how this works. Can anyone say me how does this works?

Upvotes: 0

Views: 238

Answers (2)

han
han

Reputation: 76

the sieve (epynomously) takes a huge chunk and floats out the chaff

brain wrecking this kind of algorithm (i can't even verify if it is even accurate!)

mathematically

  1. any number that can be divided by x into y, one of x and y has to be <= than the root. thus you only need to sieve up to the root, since the other divisor would already be covered

  2. all non-prime numbers must be a product of x primes (if any of its divisor is not a prime, it will have a non-1 and non-self divisor) * you won't need to sieve out multiples of non-primes too

  3. syntactically, i prefer to just declare x = [] , then you assign 1 if it is out, leave it as null if it is prime. plus i like the use of 'it', multiple declarations will be nice too, and more idiomatic use of inject() and such

im not writing any code tonight, so... i'd love to see Groovy gain some ground on Ruby, so our code really needs to be terse yet expressive and there shouldn't be too many overflowers asking what a nice piece of groovy code does

Upvotes: 0

Don Roby
Don Roby

Reputation: 41137

This is the Sieve of Eratosthenes.

What it does is go through an array of all numbers up to 1000 repeatedly, marking all multiples of each previously found prime as non-prime (represented by setting the array entry to 0), and then filters out all the zeroed entries.

Upvotes: 4

Related Questions