소수(prime)에 대하여
다음은 stackoverflow에 올라온 scala의 소수 생성 방법에 대한 간단한 분석(?!)입니다.
원 질문자의 소스는 다음과 같습니다.
그에 대한 대답으로 올라온 소스는 다음과 같습니다.
원 질문자의 소스는 다음과 같습니다.
object Euler0007 {
def from(n: Int): Stream[Int] = n #:: from(n + 1)
def sieve(s: Stream[Int]): Stream[Int] = s.head #:: sieve(s.filter(_ % s.head != 0))
def primes = sieve(from(2))
def main(args: Array[String]): Unit = {
println(primes(10001))
}
}
Scala 강좌에도 나온 에라스토테네스 방법입니다. Stream으로 끝이 정해지지 않은 연속된 자연수를 만들고 sieve 함수에서 stream의 뒷쪽 부분을 filter로 제거하는... 누군가의 비유대로 뱀이 자신의 꼬리를 먹는 것 같은 구현입니다. 문제는 프로그램 실행중 메모리 부족 에러가 발생한다는 것.그에 대한 대답으로 올라온 소스는 다음과 같습니다.
object Sieve {
val primes = 2 #:: sieve(3)
def sieve(n: Int) : Stream[Int] =
if (primes.takeWhile(p => p*p <= n).exists(n % _ == 0)) sieve(n + 2)
else n #:: sieve(n + 2)
def main(args: Array[String]) {
println(primes(10000)) //note that indexes are zero-based
}
}
앞의 소스보다는 좀 더 이해하기 쉬운 편입니다. primes 변수는 2 부터 시작하는 stream이며 sieve 함수에서는 인자로 주어진 숫자 n이 소수인지 판단하고 소수이면 stream에 포함시키고 다음 홀수를 검사하게 됩니다. 소수중 유일하게 짝수인 2는 처음에 포함시켜버리고 홀수만 검사하되 소수 p가 n의 sqrt 값보다 작은 경우까지만 검사합니다 (p => p*p <= n). 깔끔하면서 함수적 프로그래밍을 잘 구현했습니다. 앞의 소스가 sieve stream을 def로 정의해서 매번 처음부터 소수를 구하는 반면 이번은 primes stream을 val로 정의해서 이전에 구한 값들은 기억하고 있게 됩니다. 그런데, 이 답을 올린이도 이것이 정확한 에라스토테네스 방법이 아니라고 합니다.
에라스토테네스 방법으로 구현한 소스가 그 다음에 올라와 있습니다.
def sieve(n: Int) = (2 to n).foldLeft((2 to n).toSet) { (ps, x) =>
if (ps(x)) ps -- (x * x to n by x)
else ps
}
보기가 좀 애매할 수도 있는데 n 보다 작은 소수를 구하는 방법입니다. 2 부터 n까지의 숫자를 set(ps)으로 만들고 변수 x를 2부터 시작해서 1씩 증가하면서 x가 포함되어 있으면 x를 제외하고 n 보다 작은 x의 배수들을 set에서 제거하는 과정을 반복하는 것입니다. 앞의 구현과 비슷한데 앞의 방법이 매번 2부터 시작하는 소수들로 검사하는 것에 반해 이 방법은 x부터 x의 배수들을 검사하게 되므로 숫자가 커질수록 더 빠르게 계산할 수 있을것 같습니다.
루비로 두번째 방법과 비슷하게 구현해 보았습니다.
class PseudoPrime
include Enumerable
@@primes = [2]
@@suspect = 3
def initialize
@current_index = 0
end
def each
while true
yield @@primes[@current_index]
if @current_index == (@@primes.length-1)
generate
else
@current_index += 1
end
end
end
def nth(n)
while (@@primes.length < n+1)
generate
end
if block_given?
(0..n).each { |i| yield @@primes[i] }
else
@@primes[n]
end
end
private
def generate
while(@@primes.take_while{ |p| p*p <= @@suspect }.any?{ |p| @@suspect%p == 0})
@@suspect += 2
end
@@primes << @@suspect
@@suspect += 2
@current_index += 1
end
end
# example
# pp = PseudoPrime.new
# p pp.take_while{ |p| p < 100000 } // all primes under 100,000
# p pp.nth(10000) // 10001th prime
# require 'prime' // much faster! ;-P
# p Prime.take_while{ |p| p < 100000}
# p Prime.take(10001)[-1]
class가 만들어질때 소수들을 저장할 primes와 첫번째 홀수 suspect를 클래스 변수로 만들어 놓고 필요할 때마다 소수를 찾아내서 클래스 변수를 업데이트해서 여러 인스턴스가 만들어지더라도 계산을 반복해서 하지 않도록 했습니다. Enumerable 모듈을 포함했으므로 map, take, filter 등의 함수를 사용할 수 있으며 nth 함수는 0부터 시작하는 n번째 소수를 반환하는 함수입니다. 10000번째 소수를 2-3 초내에 찾을 수 있으니 예전에 몇번 만들어 보았던 프로그램보다는 효율적인것 같습니다. 하지만 언제부터인가 루비에서 prime 클래스를 제공하고 그걸 사용하면 1초도 걸리지 않고 답을 찾을 수 있다는 것...
댓글