Euler project number 7 in the scheme

Question

Here is the question:

Having listed the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th is 13.

What is the 10001st number of primes?

Here is my solution:

#lang racket (define (search-limit num) (+ (floor (sqrt num)) 1)) (define (search-list num) (stream->list (in-range 2 (search-limit num)))) (define (divided? num x) (= (remainder num x) 0)) (define (list-of-dividers num) (filter (lambda (x) (divided? num x)) (search-list num))) (define (prime? num) (= (length (list-of-dividers num)) 0)) (define (problem_7 current_prime primes counter) (cond [(< primes 10001) (cond [(prime? counter) (problem_7 counter (+ primes 1) (+ counter 1))] [else (problem_7 current_prime primes (+ counter 1))])] [else current_prime])) (problem_7 0 0 0) 

It works, but it works slowly. I am sure there is a better solution.
Can you give me a more schematic solution?

Answer 1

I did this as follows, which takes less than 1 second on my computer (your version took about 12.5 seconds):

 #lang racket (define (divides? n div) (= (remainder n div) 0)) (define (prime? n) (prime-helper n 2)) (define (prime-helper n start) (cond ((> start (sqrt n)) #t) ((divides? n start) #f) (else (prime-helper n (+ 1 start))))) (define (prob7_helper n count) (cond ((= 10001 count) (- n 1)) ((prime? n) (prob7_helper (+ 1 n) (+ 1 count))) (else (prob7_helper (+ 1 n) count)))) (define (prob7) (prob7_helper 2 0)) (prob7) 

There are, of course, faster implementations (prime? n) , but that does the trick for me.

Answer 2

Composite numbers always have a smaller prime as a divisor; prime numbers never have a smaller prime number as a divisor. Since you are consistently generating primes, you can use this fact by performing your simplicity test, just try to divide your candidate into a list of smaller primes. (This, by the way, is a variation of the Sith Eratosthenes method.)