检查指定范围内连续奇数的素数

Question

以下程序查找给定数字 n 的最小整数除数（大于 1）。它通过测试 n 是否可以被以 2.

开头的连续整数整除来以一种直接的方式做到这一点

n 是质数当且仅当 n 是它自己的最小约数。

(define (square x) (* x x))

(define (divisible? a b)
  (= (remainder a b) 0))

(define (find-divisor n test)
  (cond ((> (square test) n) n)
        ((divisible? n test) test)
        (else (find-divisor n (+ test 1)))))

(define (smallest-divisor n)
  (find-divisor n 2))

(define (prime? n)
  (= (smallest-divisor n) n))

如何编写一个程序来检查指定范围内的连续奇数的素数？

(define (search_for_primes from to)
   (cond ((> from to) false)
         ((prime? from) (display from))
         (else (search_for_primes (+ 1 from) to))))

我的解决方案只是将 1 写入输出。

Answer 1

你绝对应该从在范围内做一个有效的筛子（比如 Eratosthenes 的筛子）开始，以有效地捕获多个小素数。如果您的数字很小，那么最多 sqrt(n) 就足够了。（这足以解决例如欧拉计划问题。）

如果您的范围小而数字大，则使用它来获得 "likely primes"，然后对每个使用您最喜欢的素性测试（请参阅 https://en.wikipedia.org/wiki/Primality_test 了解一些选项）。

如果你的范围很大而且你的数字很大......你就有问题了。 :-)

Answer 2

A cond 将在 第一个 匹配处停止并仅执行相应的表达式。因此，如果您执行 (search_for_primes 1 xxx)，1 会被 错误地 识别为素数，并且过程会停在那里。

你想要的是这样的

(define (search_for_primes from to)
  (unless (> from to)
    (when (prime? from)
      (display from)
      (display " "))
    (search_for_primes (+ 1 from) to)))

无论您是否找到素数，递归都会完成。

测试：

> (search_for_primes 2 100)
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

检查指定范围内连续奇数的素数

Checks the primality of consecutive odd integers in a specified range

algorithm

scheme