Advertisement
triclops200

O(sqrt(n)) recursive primality test

Sep 19th, 2012
262
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Scheme 0.56 KB | None | 0 0
  1. (define prime? (lambda (n)
  2.     (cond
  3.         ((< n 2)
  4.             #f  
  5.         )  
  6.         ((= n 2)
  7.             #t  
  8.         )  
  9.         ((= (modulo n 2) 0)
  10.             #f  
  11.         )  
  12.         (#t
  13.             (prime_h 3 (sqrt n) n)
  14.         )  
  15.     )  
  16. ))
  17. (define prime_h (lambda (i n m)
  18.     (cond
  19.         ((>= i n)
  20.             #t  
  21.         )  
  22.         ((= (modulo m i) 0)
  23.             #f  
  24.         )  
  25.         (#t
  26.             (prime_h (+ i 2) n m)
  27.         )  
  28.     )  
  29. ))
  30. (display (prime? 689024813))
  31. (display (prime? 689024815))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement