Groovy Prime Numbers
by RJ Salicco on May.11, 2009, under Development
The other day I wanted to prove the power of Groovy to a few more core Java developers. I sat down and played with a little script that I think proves the power, or ease of use, of Groovy while having fun with number theory. My goal was to have a Collection that contains Prime Numbers calculated from a given range of numbers x to y, or in Groovy syntax x..y. I am taking a few things for granted with this script. For example, I know that 2 is the lowest Prime Number (it helps simplify the algorithm) and that 1 is not a Prime Number. So here’s the script:
def t = 1..100
def v = []
t.each { n ->
(2..n).each { d ->
if(n % d == 0 && n != d)
v.add(n)
}
}
println t - v - 1
We have our range of numbers t and we are capturing the non-Prime numbers and adding them to our Collection v. The final line of the script is doing a lot of groovy work for us that would take a few more lines of code with plain Java syntax. What is it doing for us? It is taking our range of numbers t and subtracting (removing) our non-Prime numbers collected in v. This line is also removing the number 1 because we know that 1 is not a Prime Number. Finally, it is printing the result like so:
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
Very cool stuff. Now, I know that many of us are rarely building a Collection of Prime Numbers and I know this script does not do things in a timely manner with a range like 1..10000 (it took a couple of minutes), but I am sure this feature of Collections in Groovy can be utilized in many ways in my development.
14 Comments for this entry
-
Welcome to theJavaJar!
Thanks for dropping by! Feel free to join the discussion by leaving comments, and stay updated by subscribing to the RSS feed
-
May 12th, 2009 on 2:25 pm
Yes, short and powerful, but unfortunately extremely slow compared to java versioin for Project Euler usage
btw, you example could be optimized in many points
May 13th, 2009 on 7:56 am
Yes, short and powerful, but unfortunately extremely slow compared to java versioin for Project Euler usage
btw, you example could be optimized in many points
May 13th, 2009 on 8:28 am
I probably should have gave this post a better title. I just used Prime Numbers because I really just needed 2 collections of something to get to the important line,
println t - v - 1. I really just wanted to show how easy it is to take one collection of numbers, 1..100, and remove all non-Prime Numbers that exist in another collection with a minus (-) operator and display the results.May 13th, 2009 on 5:44 pm
Wouldn’t it be even more illustrative to take the range 1..100 and successively remove the collections [1], [4, 6, 8, ...], [6, 9, 12, ...] … [2n, 3n, 4n, ...]?
For my part, I think partitioning might be even more interesting as a demonstration of Groovy:
(1..1000).groupBy { n ->
n != 1 && ((2.. println “${key}:\t${val}” }
(Code not fully tested.)
May 13th, 2009 on 5:47 pm
Oops, I don’t know what happened to my code there. I’ll try once more:
(1..1000).groupBy { n ->
n != 1 &&
((2..
println “${key}:\t${val}”
}
May 13th, 2009 on 5:51 pm
Sorry for cluttering up your comment space. I think the less-than character is the culprit. Final try:
(1..1000).groupBy { n ->
n != 1 &&
((2..(n-1)).every{n % it != 0}) ?
‘primes’ : ‘nonprimes’
}.each { key, val ->
println “${key}:\t${val}”
}
May 13th, 2009 on 6:02 pm
No worries. I appreciate the feedback.
May 14th, 2009 on 6:27 am
I find it very stimulating to discuss this kind of thing. Writing optimally efficient algorithms is obviously useful, and writing the shortest/most obfuscated/etc possible source is a fun challenge.
Finding the best way to express a concept in a programming language, and thus illustrating that language’s ‘expressiveness’, however, goes beyond both useful and fun.
Anyway, I came up with the code to implement the Eratosthenesian notion I mentioned yesterday:
def t = 1..1000
t -= [1]
(2..Math.sqrt(t.last())).each { n ->
t -= ((2*n)..(t.last())).step(n)
}
println t
To me, that’s an executable specification.
May 15th, 2009 on 10:42 pm
Some nice solutions and I particularly like Lewerin’s solution but it is still rather slow for say 100,000.
There are same simple things to improve the performance
1. Removing evements from an ArrayList [...] is very expensive. So keep the list size the same and set the the value at an index to zero if the number is not prime.
So if x is not prime then t[x] = 0
2. The outer list outer list has to go over 2 and odd numbers only.
[2, (3..L).step(2)].flatten() will do the trick
(L is sqrt(max_num))
so we get the list [2,3,5,7,9...]
So where does the sqrt come from?
Well… if X is a composite number (non prime) then
X = A*B
let say we always arrange it so that A is always the smallest value such that X = A*B, then the largest value for A can be sqrt(X). (beccause X = sqrt(X)*sqrt(X) )
for the inner loop we don’t have to start fro 2*n if n > 2, because we have already removed all multiples of 2. If n > 3 we don’t have to start from 3*n because we have removed all multiples of 3 and so on.
By that logic we can start from n*n; also n would itself have to be prime, otherwise it already has been removed. So we remove – n*n, n*(n+1), n*(n+2) …
But wait a minute if n is prime and n > 2 the n is also odd; and n+1 must be even (a multiple of 2), but we have removed all those. So we actually need to remove
n*n, n*(n+2), n*(n+4), …
so for n > 2 the step size in the inner loop is 2*n
def t = (0..10000).flatten()
t[0]=0; t[1]=0; // 0 and 1 are not prime
def L = Math.sqrt(t.size())
( [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 })
}
}
result = t.findAll({ it != 0 })
May 15th, 2009 on 10:53 pm
Sorry the code again and it is very fast, for 100,000 it takes less than a second:
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 })
May 24th, 2009 on 10:12 am
Hi, courteous posts there
express’s recompense the gripping information
May 28th, 2009 on 4:11 pm
Thanks, good article.
June 1st, 2009 on 10:12 pm
da best. Keep it going! Thank you
June 4th, 2009 on 9:51 am
@Nurul – very good!