hangscer

scala写算法-选筛法求素数

2017/06/15

选筛法,用空间换时间。
核心思想就是素数的倍数一定不是素数。

上代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
object Main extends App {
val array=new Array[Int](1000)
for(i<- 2 until array.length){array(i)=1}//初始化
def isPrime(n:Int)= !(2 until n ).exists(i=> n%i==0)
(2 until array.length).foreach{index=> array(index) match {
case 0 => //这个索引值不是素数
case _ =>
if(isPrime(index)){
println(s"${index}是素数,那么它的倍数不是素数")
Stream.from(index).takeWhile(i=> i*index < array.length).foreach(i=> array(i*index)=0)
//标记为0
}
}}
}