Mersenne-Primzahlen mit Lucas-Lehmer-Primalitätstest finden

Question

Ich möchte in Scala eine Stream implementieren, um Mersenne-Primzahlen mit dem Lucas-Lehmer-Primalitätstest zu finden. Ich habe bereits:

object Main { 
    //Mersenne Numbers: 
    def msrn():Stream[BigInt] = 7#::msrn.map(_*2+1) 
    def s():Stream[BigInt] = 14 #:: s.map(n => n*n-2) 
    lazy val zips = s.zip(msrn) 
    def main(args: Array[String]) { 
    zips take 7 foreach println 
    } 
} 

Was ich jetzt tun müssen, ist alle Mersenne-Zahlen (Elemente in msrn) finden, die das Element in s teilt und schreiben sie in einem Stream.

Edit: es wurde gelöst:

object Main { 
    def msrn():Stream[BigInt] = 7#::msrn.map(_*2+1) 
    def s():Stream[BigInt] = 14 #:: s.map(n => n*n-2) 
    lazy val zips = s.zip(msrn).filter(x=>x._1%x._2==0) 
    def mersennePrimeStream():Stream[BigInt] = zips.map(x => x._2) 
    def main(args: Array[String]) { 
    mersennePrimeStream take 4 foreach println 
    } 
} 

Gibt es eine Möglichkeit, obwohl es kürzer zu machen?

Answer 1

Sie viel schneller, wenn Sie die s-Sequenz modulo der Mersennezahl Sie testen berechnen:

object Main { 
    def s(k: Int, m: BigInt) = Iterator.iterate(BigInt(14))(n => (n * n - 2) % m) drop k next 
    lazy val msrn: Stream[(Int,BigInt)] = (0,BigInt(7)) #:: msrn.map(t => (t._1 + 1, t._2 * 2 + 1)) 
    val mersennePrimeStream = msrn filter(x => s(x._1, x._2) % x._2 == 0) map (_._2) 
    def main(args: Array[String]) = mersennePrimeStream take 10 foreach println 
}