groovy: 也来玩玩梅森数

在javaeye的ruby版，看见ruby算梅森数组的一个贴，

很有趣啊。

我这里弄一个groovy的实现。

什么是梅森数组：

http://zh.wikipedia.org/w/index.php?title=%E6%A2%85%E6%A3%AE%E7%B4%A0%E6%95%B0&variant=zh-cn

给一个原始的实现：

boolean isPrime(n)


 { 


    if(n==1) return false;


    if(n==2) return true;


     for(i in 2..Math.round(n**(0.5))){println i;if(n%i==0) return false}


     return true;


 }





mersennes = [];


(2..31).each{n=2**(it)-1;if(isPrime(n)) mersennes << n}


println mersennes;

我的机器耗时2秒算到n=31的梅森数2147483647

,达到欧拉的水平.O^O

之后就很难了，等了5分钟也没算出下一个梅森数。

继续优化：

算法分析：

f(n)=2**n-1

f(n+1)=2**(n+1)-1=(2**n)*2-1=(2**n)*2-2+1=2(2**n-1)+1=2f(n)+1

==>

f(n+1)=2f(n)+1

eg:

f(1)=2**1-1=1

f(2)=2*f(1)+1=3

f(3)=2f(2)+1=7

f(4)=2f(3)+1=15

...

boolean isPrime(n)
 { 
    if(n==1) return false;
    if(n==2) return true;
     for(i in 2..Math.round(n**(0.5))){if(n%i==0) return false}
     return true;
 }

cache = new HashMap();

def function(n)
{
    if(cache.getAt(n)!=null) return cache.getAt(n)
    value = (n==1?1:2*function(n-1)+1)
    cache.putAt(n, value);   
    return value;
}

(2..31).each{v=function(it);if(isPrime(v)) println "f"+it+"="+v}

还是算到f31，用时200毫秒，速度提高了一个数量级。

f61还是出不来。

大数据在groovy中默认为double的，估计要换成BigDecimal试一下。