sicp-ex-1.33


a. The filtered_accumulate procedure is not optimized at all.. We'll use the prime? procedure defined earlier in the book with a small fix to make (prime? 1) -> #f.

  (define (smallest-div n) 
    (define (divides? a b) 
      (= 0 (remainder b a))) 
    (define (find-div n test) 
       (cond ((> (sq test) n) n) ((divides? test n) test) 
             (else (find-div n (+ test 1))))) 
    (find-div n 2)) 
  
   (define (prime? n) 
     (if (= n 1) false (= n (smallest-div n)))) 

Filtered accumulate procedure:

  (define (filtered-accumulate combiner null-value term a next b filter) 
  (if (> a b) null-value 
      (if (filter a) 
          (combiner (term a) (filtered-accumulate combiner null-value term (next a) next b filter)) 
          (combiner null-value (filtered-accumulate combiner null-value term (next a) next b filter))))) 

a. Sum of squares of prime numbers procedure:

  (define (sum-of-prime-squares a b) (filtered-accumulate + 0 sq a inc b prime?)) 

Test example: (sum-of-prime-squares 1 5)

ans. 38

b. Product of all positive integers les than n that are relatively prime to n

 (define (gcd m n) 
   (cond ((< m n) (gcd n m)) 
         ((= n 0) m) 
         (else (gcd n (remainder m n))))) 
  
 (define (relative-prime? m n) 
 (= (gcd m n) 1)) 
  
 (define (product-of-relative-primes n) 
   (define (filter x) 
     (relative-prime? x n)) 
 (filtered-accumulate filter * 1 identity 1 inc n)) 

Example: (product-of-relative-primes 10) 189


<< Previous exercise (1.32) | sicp-solutions | Next exercise (1.34) >>