91575


Scheme言語を使って与えられたｎまでの素数を出し、そのリストが昇順であるコードを書いています。(またcondとconsを使う必要があります)

例）１０を与えられたら、２，３，５，７をプリントする

素数を確認するコードはたぶん機能すると思うのですが、昇順にするためのコードがうまくいきません。  
どなたか何かいい案をお持ちでしたらシェアしていただけると幸いです。  
よろしくお願いします。

自分のコード

[code]

    (define (prime n)
        (cond(
           (if (< n 2) )
           (if (= n 2)2)
           (else (= isPrime checkPrime(n,2)))
              (if(isPrime)(prime(- n 1))
              (else (prime(- n 1))))))
    
    (define (checkPrime n i))
       (cond(
          (if( = i n) #t)
          (if(= (modulo n i) 0)#f)
          (else (checkPrime(n,(+ n 1))))))
    
[/code]


CC BY-SA 4.0
2022-10-12T22:57:55.640
91572
2022-10-13T05:06:20.570
2022-10-13T00:59:06.153
3060
54742
question
scheme
n以下のすべての素数を含むリストを返す関数


色々な方法がありますが素朴で効率が良い方法としては「エラトステネスの篩」が知られています。
小さな値から順番に素数を探すのですからすでに見つかった素数で割れるかどうかを検査すればよいのです。 (最初にわかっている素数として 2 だけ与える。)
また、あらたに見つかった素数は `cons` で結果のリストに追加していきます。
線形リストの頭に追加するのはコストが小さいのでこういった形で結果を蓄積するのは Scheme (を含む LISP 系言語) では一般的なイディオムです。

しかしながらリストの頭に結果を追加していく方法だと見つかった逆の順番になるので最後に `reverse` でリストを逆転します。

以上を踏まえてコードにすると以下のようになります。 (実際には割るのを試すのは `n` の平方根までで十分ですが手続きの分割のしやすさのため省略しています。
また、ここでは R5RS を前提としていますが Scheme
の仕様には改定があって若干の非互換が存在するので想定する版によっては動かない可能性があります。)

[code]

    (define (divide? n1 n2)
      (zero? (modulo n1 n2)))
    
    (define (divide-any? n ls)
      (do ((ls ls (cdr ls)))
          ((or (null? ls)
               (divide? n (car ls)))
           (not (eqv? '() ls)))))
    
    (define (primes-less-than n)
      (let loop ((result '(2))
                 (i 3))
        (cond ((>= i n) (reverse result))
              (else (loop
                     (if (divide-any? i result) result (cons i result))
                     (+ i 2))))))
    
    ;; テストケース。 100 以下の素数を返す
    (write (primes-less-than 100))
    
    
[/code]


CC BY-SA 4.0
2022-10-13T05:06:20.570
91575
2022-10-13T05:06:20.570
3364
91572
answer