Lucas-Lehmer 소수 테스트로 메르 센 소수를 찾는 것

Question

Lucas-Lehmer 소수 테스트로 메르 센 소수를 찾는 스칼라에 Stream을 구현하고 싶습니다. 나는 이미 : 지금해야 할 일은

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 
    } 
} 

는 s의 요소를 분할하는 모든 메르 센 번호 (msrn의 요소)를 찾아서는 Stream에 쓰기입니다.

편집 : 그것을 해결 :

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 
    } 
} 

비록 짧게 만들 수있는 방법이 있나요? 당신이의 시퀀스를 계산하는 경우가 훨씬 빠릅니다

Answer 1

는 테스트중인 메르 센 수를 모듈로 :

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 
}