scheme - 方案中的欧拉项目#7

Question

这里有一个问题:

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

What is the 10001st prime number?

这是我的解决方案:

#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)

它可以工作，但工作速度很慢。我确信有更好的解决方案。
你能给我更方案的解决方案吗？

Answer 1

我按照以下方式进行操作，在我的计算机上花费了不到 1 秒(您的版本大约花费了 12.5 秒):

#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)

当然有更快的 (prime? n) 实现，但这对我来说很有效。