최원태
가입: 2006년 9월 16일 올린 글: 369
|
올려짐: 2008년10월1일 14:33 주제: 실습용 코드 : is-prime? accumulate |
|
|
PLT-scheme 용 primality check 함수 is-prime?입니다.
에라토스테네스의 채로 구현했도, 약간 최적화되어있습니다.
primality check의 구현 방법은
에라토스테네스의 채, 확률적 방법, 결정론적 방법 크게 세가지 지류가 있습니다.
수학에 관심있으신분은, 본인의 방법으로 구현해봐도 재미있을 문제입니다.
코드: | (define (interval-list s e)
(if (> s e) () (cons s (interval-list (+ s 2) e))))
;prime number list generator by Ozan Yigit
;--------------------------start----------------------------
(define (sieve l)
(define (remove-multiples n l)
(if (null? l)
'()
(if (= (modulo (car l) n) 0) ; division test
(remove-multiples n (cdr l))
(cons (car l)
(remove-multiples n (cdr l))))))
(if (null? l)
'()
(cons (car l)
(sieve (remove-multiples (car l) (cdr l))))))
(define (primes<= n)
(cond
((= n 2) (list 2))
((< n 2) ())
(else (cons 2 (sieve (interval-list 3 n))))))
;---------------------------end-----------------------------
(define (is-prime? n)
(call-with-current-continuation
(lambda (k)
(if (<= n 1) #f
(begin
(for-each (lambda (x) (if (= (modulo n x) 0) (k #f) #t))
(primes<= (floor (sqrt n))))
#t)))))
|
많이 보았을, accumulate 구현입니다.
코드: | (define (accumulate f c l)
(cond ((null? l) c)
((not (list? l)) (error "accumulate : 3rd arg : must be list type"))
(else (f (car l) (accumulate f c (cdr l)))))) |
|
|