# SICP 1.2 exercises cont. 10

**Posted:**January 16, 2013

**Filed under:**Improving, SICP Leave a comment

**1.22**

(define (search-for-primes current largest) (cond ((< current largest) (if (not ( even? current)) (timed-prime-test current)) (search-for-primes (+ 1 current) largest))) )

for greater than 1,000,000,000 …

1000000001 1000000003 1000000005 1000000007 *** 7 1000000009 *** 6 1000000011 1000000013 1000000015 1000000017 1000000019 1000000021 *** 7

and for greater than 10,000,000,000…

10000000001 10000000003 10000000005 10000000007 10000000009 10000000011 10000000013 10000000015 10000000017 10000000019 *** 21 10000000021 10000000023 10000000025 10000000027 10000000029 10000000031 10000000033 *** 21 10000000035 10000000037 10000000039 10000000041 10000000043 10000000045 10000000047 10000000049 10000000051 10000000053 10000000055 10000000057 10000000059 10000000061 *** 21

So 10 billion takes about 3, which is around root of 10, times as long as 1 billion, so it works as expected.

**Comments:** The main benefit from this exercise was scheme practice. I also needed to use larger numbers than the question asks for – probably because computers are just faster these days. I also had to find an implementation of runtime for guile, which I found here.

**1.23**

Implementing next is trivial.

(define (next input) (if (= 2 input) 3 (+ input 2)))

The times I get for the first 3 primes greater than 1 billion are

1000000007 *** 4 1000000009 *** 5 1000000021 *** 5

And for the first 3 prime numbers greater than 10 billion

10000000019 *** 13 10000000033 *** 14 10000000061 *** 13

We can see that it takes about 2/3 of the time instead of about 1/2 of the time. I think this is because the next procedure is more expensive than a simple + procedure.

**1.24**

I would expect 1,000,000 to take around twice as long as 1,000.

1000000007 *** 1 1000000009 *** 1 1000000021 *** 1

and then doubling the number of zeroes…

1000000000000000003 *** 3 1000000000000000009 *** 2 1000000000000000031 *** 2

It seems about right, although likely anything could have gone wrong.

**Comments:** Caught up a little bit although still slow. A better time function would have been nice, but I am being lazy.