极客教程Scala 埃拉托色尼筛
古希腊数学家埃拉托色尼（Eratosthenes of Cyrene）发现了一种神奇的算法来寻找质数。
本文将在Scala中执行这一算法。
第1步 ：创建一个Int流
def numberStream(n: Int):
Stream[Int] = Stream.from(n)
println(numberStream(10))
上述步骤的输出是 Stream(10, ?)。
第2步： 埃拉托什尼函数的筛子
// Defining Sieve of Eratosthenes
def sieve_of_Eratosthenes(stream: Stream[Int]):
Stream[Int] = stream.head #:: sieve_of_Eratosthenes(
(stream.tail)
filter (x => x % stream.head != 0)
)
println(sieve_of_Eratosthenes(numberStream(10)))
上述步骤的输出是 Stream(10, ?) 。
第3步： 提取 “N “数量的素数
val no_of_primes = sieve_of_Eratosthenes(numberStream(2))
// Selecting number of primes
println(no_of_primes)
(no_of_primes take 7) foreach {
println(_)
}
上述步骤的输出是
Stream(2, ?)
2
3
5
7
11
13
17
下面是完整的程序
def numberStream(n: Int):
Stream[Int] = Stream.from(n)
println(numberStream(10))
// Defining Sieve of Eratosthenes
def sieve_of_Eratosthenes(stream: Stream[Int]):
Stream[Int] = stream.head #:: sieve_of_Eratosthenes(
(stream.tail)
filter (x => x % stream.head!= 0)
)
println(sieve_of_Eratosthenes(numberStream(10)))
val no_of_primes = sieve_of_Eratosthenes(numberStream(2))
// Selecting number of primes
println(no_of_primes)
(no_of_primes take 7) foreach {
println(_)
}
输出
Stream(10, ?)
Stream(10, ?)
Stream(2, ?)
2
3
5
7
11
13
17
从代码中得到的启示
- 使用stream.form()，创建了一个正在生成连续的数字的流。而这个数字是从参数开始的。
- 一个数字流被赋予 “sieve_of_Eratosthenes “方法。这个方法通过过滤掉元素，懒洋洋地生成连续的元素。
下面是完整的工作代码和解释：
工作：abc()方法在filter()方法中插入了debug语句。如果一个元素不能被头部平均分割，流会把它当作一个好的元素。代码将其打印出来并返回true。否则就打印被过滤掉的序列，最后返回流。
在sieve_of_Eratosthenes方法中做了一些修改，以便使用流创建-abc()方法。从递归流中取出元素并打印出来。
object Sieve extends App {
def abc(s: Stream[Int], head: Int) = {
val r = s filter {
x => {
if (x % head != 0) {
println()
println(s"{x} is not evenly divisible by{head}")
true
}
else {
println()
println(s"{x} is evenly divisible by{head}. So Discard ${x}")
false
}
}
}
r
}
def numberStream(g: Int): Stream[Int] = Stream.from(g)
def sieve_of_Eratosthenes(stream: Stream[Int]):
Stream[Int] = stream.head #:: sieve_of_Eratosthenes(
abc(stream.tail, stream.head))
val no_of_primes = sieve_of_Eratosthenes(numberStream(2))
(no_of_primes take 7) foreach {
println(_)
}
}
输出:
2
3 is not evenly divisible by 2
3
4 is evenly divisible by 2. So Discard 4
5 is not evenly divisible by 2
5 is not evenly divisible by 3
5
6 is evenly divisible by 2. So Discard 6
7 is not evenly divisible by 2
7 is not evenly divisible by 3
7 is not evenly divisible by 5
7
8 is evenly divisible by 2. So Discard 8
9 is not evenly divisible by 2
9 is evenly divisible by 3. So Discard 9
10 is evenly divisible by 2. So Discard 10
11 is not evenly divisible by 2
11 is not evenly divisible by 3
11 is not evenly divisible by 5
11 is not evenly divisible by 7
11
12 is evenly divisible by 2. So Discard 12
13 is not evenly divisible by 2
13 is not evenly divisible by 3
13 is not evenly divisible by 5
13 is not evenly divisible by 7
13 is not evenly divisible by 11
13
14 is evenly divisible by 2. So Discard 14
15 is not evenly divisible by 2
15 is evenly divisible by 3. So Discard 15
16 is evenly divisible by 2. So Discard 16
17 is not evenly divisible by 2
17 is not evenly divisible by 3
17 is not evenly divisible by 5
17 is not evenly divisible by 7
17 is not evenly divisible by 11
17 is not evenly divisible by 13
17