1

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

例)10を与えられたら、2,3,5,7をプリントする

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

自分のコード

(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))))))
3
  • 素数のリストを求めることができているのであれば、分からないのは「昇順にソートする」ではないですか?タイトルは質問内容に見合ったものを意識してください。
    – cubick
    Commented 2022年10月13日 1:06
  • また、過去の質問には回答が付いている状態なので、放置したままにせず何かしらのアクションを行ってください。参考ヘルプ: 自分の質問に誰かが回答してくれたらどうしたらいいですか?
    – cubick
    Commented 2022年10月13日 1:08
  • Scheme の文法から間違っています。cond 式の使い方について見直してみて、質問文を直してみてください。今「素数かどうか判定する関数」と「数の一覧から素数だけ抜き出して返す関数」のふたつに分けて実装なさろうとしているようなので、とりあえず「素数かどうか判定する関数」だけ単独で動かしてみて確かめていくとよさそうです。
    – nekketsuuu
    Commented 2022年10月13日 2:32

1 件の回答 1

2

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

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

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

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

4
  • コメントありがとうございました。実行してみたのですが、いくつかテストを行ってみたのですが、いくつか上手くいきませんでした。うまくいかなかったテストケースは今のところ1,3,11です。1の時は空白?になるようにしたいのですが、2と表示され、3の時は2,3が表示されるようにしたいのですが、2のみの表示。11の時は2,3,5,7,11と表示されるようにしたいのですが、11以外の数字のみの表示でした。色々自分でもコードを少しいじってみたのですがどれもうまくいきませんでした。度々申し訳ございませんが、何か方法はありますかね?
    – yojozaok21
    Commented 2022年10月15日 4:45
  • (cond ((>= i n) (reverse result)) の=を消すと上の1以外のテストーケースは上手くいくのですが、1だけ上手くいきません。
    – yojozaok21
    Commented 2022年10月15日 5:03
  • 「以下」なのにうっかり n 自体を含まない形にしてますね。 すいません。 手法のおおまかなコンセプトがわかればよいかと思ってちょっと雑に書いてました。 >= を > にするのは正しい修正です。 n が 1 以下のときにも結果が 2 を含んだ形にしてしまうのは既知の整数として問答無用で 2 を最初から含んだものにしているからで、この手法自体が n は 2 以上であることということが大前提 (事前条件) になってしまっています。 この前提から外れる n が与えられたときの処理は完全に場合分けするのが妥当な方法です。 つまり最初に n が 1 以下だったら '() を返すという分岐を追加してください。 Commented 2022年10月15日 10:16
  • (define (primes n)のあとに(if (<= n 1) '()のようにnが1以下の場合に()と返すコードを書いたらちゃんと動きました。最初のお返事とコメントでのお返事ありがとうございました。非常に勉強になりました。
    – yojozaok21
    Commented 2022年10月16日 1:32

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。