使用 Lucas–Lehmer 素数测试寻找 Mersenne 素数

Question

我想在 Scala 中实现 Stream 以使用 Lucas-Lehmer 素数测试寻找 Mersenne 素数。我已经有：

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

我现在需要做的是找到所有梅森数（msrn中的元素）将s中的元素划分并写在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

如果你计算 s 序列模你正在测试的梅森数，你会快得多：

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
}

使用 Lucas–Lehmer 素数测试寻找 Mersenne 素数

Finding Mersenne primes with Lucas–Lehmer primality test

math

primes

scala