質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.47%
Python 3.x

Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

意見交換

クローズ

37回答

4315閲覧

素数を書き出すプログラムの良しあしを判断してほしい

saichanian

総合スコア22

Python 3.x

Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

1グッド

3クリップ

投稿2023/07/22 09:16

編集2023/07/22 09:27

1

3

実現したいこと

素数を書き出すプログラムの良しあしを判断してほしい

前提

現在Pythonにて、簡単な素数判定プログラムを作成しました。

以下のコードについて、わかりにくい点や修正すべき点、バグが入り込む余地やさらに良いプログラムがあれば、ご教示いただきたいです。
現在コーディングテストに向けての学習を行っておりますので、テストでの合格基準をもとに判断していただけますと非常にありがたいです。

該当のソースコード

Python

1for num in range(2, 100): 2 i = 2 3 x = num 4 while i < x: 5 if num % i == 0: 6 break 7 else: 8 x = num // i 9 i += 1 10 else: 11 print(num)

まず、このコードを説明いたします。

素数というのは、「一とその数自身との外には約数がない正の整数。」ということですので、例えば100が素数かを判定するために、2から99までの数字で割り切れるかを見ることで、素数かどうかを判定することもできます。
しかしながら、それでは素数かを判定する数字が大きくなればなるだけ、プログラムの実行が重くなってしまいます。

そこで上記のプログラムでは、約数があるかをもとに考えました。

例えば97が素数かを判断するためにまず2で割ると
97÷2=48 あまり1
となるので、48以上の数字に約数がないことがわかります。また、
97÷3=32 あまり1
なので、32以上の数字にも約数がないことがわかります。
このように、2, 3, 4…と小さな数字で順に割っていくことで素数かを判定すると同時に、判定しなければならない数値の範囲を狭めています。

上記のコードのfor文にて、num = 17の時を考えますと、

Python

1i = 2 2x = num #x = 17 3while i < x: #while文1回目:2 < 17が成り立つ 4 if num % i == 0: # 成り立たない 5 break 6 else: 7 x = num // i # xに17 // 2(=8)を代入 8 i += 1 #iに3を代入 9else: 10 print(num)

次、i = 3の時

Python

1while i < x: #while文2回目:3 < 8が成り立つ 2 if num % i == 0: # 成り立たない 3 break 4 else: 5 x = num // i # xに17 // 3(=5)を代入 6 i += 1 #iに4を代入 7else: 8 print(num)

次、i = 4の時

Python

1while i < x: #while文3回目:4 < 5が成り立つ 2 if num % i == 0: # 成り立たない 3 break 4 else: 5 x = num // i # xに17 // 4(=4)を代入 6 i += 1 #iに5を代入 7else: 8 print(num)

次、i = 5の時

Python

1while i < x: #while文4回目:5 < 4なので成り立たない 2 if num % i == 0: # 実行されない 3 break 4 else:# 実行されない 5 x = num // i 6 i += 1 7else: 8 print(num) #num(=17)が出力される

上記のコードについて、わかりにくい点や修正すべき点、バグが入り込む余地等があれば、ご教示いただきたいです。

yuma.inaura👍を押しています

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

回答37

#1

meg_

総合スコア10583

投稿2023/07/22 09:56

現在コーディングテストに向けての学習を行っておりますので、テストでの合格基準をもとに判断していただけますと非常にありがたいです。

「コーディングテスト」とはどのようなテストを指しているのでしょうか?「テストでの合格基準をもとに判断」とありますが、何らかの基準は開示されているのでしょうか?

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

#2

saichanian

総合スコア22

投稿2023/07/22 10:07

meg_様

ご回答、誠にありがとうございます。

コーディングテストとは、就職活動において就活生のプログラミング能力を測るためのものです。
説明不足となってしまい、申し訳ございません。

「合格基準」はおそらく各企業で設定されているはずですので、はっきりとした基準は誰にもわからないものと思われますが、過去にそのようなテストをご受験いただいた方は、そのご経験をもとにアドバイスをしていただけますと幸いです。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

#3

winterboum

総合スコア23349

投稿2023/07/22 10:34

評価に基準の一つに計算量が少ないか というのがあるかと思うので、その観点で。

なにで割るか、について2点
1.「となるので、48以上の数字に約数がないことがわかります」
これに気がついたのは立派ですが、 sqrt(num) まで探せば良い ということと同義です。i を増やす毎に上限を更新する必要がなくなります
2. i が変わる毎に2から一つずつ調べ直してますが、それまでにわかった素数をしまっておいて、それら全てで割り切れなければ OK です。
ちょっと心配か、その先 sqrtまで、なら大丈夫ですね。前半でOKと証明できたら後半省略。
なんとかの篩 ってアルゴリズムだったような。調べて。

割られる数について2点

  1. 2 以外の偶数で調べる必要はありません。
  2. それを拡張すると、2,3 の後は 6n ± 1 について調べればOK

 まぁ、、2,3 辺りは計算無しで出力しちゃったって良いような。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

#4

ikedas

総合スコア4337

投稿2023/07/22 10:38

コードの動作が正しいかは確認していませんが、いくつか感想を。

while i < x: ... x = num // i
  • 試し割りの結果の商も利用して調べる範囲を狭めるというのは、いいアイディアだと思います (numの平方根以下だけを調べていることになりますから)。
    ちなみに、組み込み関数divmod()を使うと商と剰余を一度に求められるので、少しだけスピードアップできるかもしれません。

ただ、まだ無駄があるように思います。

for num in range(2, 100):
  • 2以外の素数はすべて奇数です。numとしてはrange(3, 100, 2)の範囲を調べればいいです。
    • なおちなみに、3よりも大きい素数は必ず 6n±1 (n>=1) の形になります (証明は簡単です)。この性質を使えばさらにnumを調べる対象を減らせます。
i += 1 else: print(num)
  • 試し割りをするときのiには、すでに素数だとわかっている数だけを使えば十分です。素数だとわかったnumを出力するだけでなく、リストにでもためておいて以降の数の試し割りに使えばいいですね。

とりあえず思いついたことだけです。

  • エラトステネスの篩についても調べてみるとよいでしょう。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

#5

退会済みユーザー

退会済みユーザー

総合スコア0

投稿2023/07/22 10:42

編集2023/07/22 10:48

数学のトリックでも何でもないですが、Numbaで@njit()すると速度が劇的に変わります。「Pythonを使う条件は良いとして、何もライブラリを使うな」という制約がなければですが…。


エラストテネスの篩のような正確さはありませんが、ミラーラビンテストは普通の人(≒暗号処理を生業にしている人以外)には実用足る精度で素数判定できます。

参考:確率的素数判定法 vs. エラトステネスの篩@技術メモさん

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

#6

saichanian

総合スコア22

投稿2023/07/22 11:26

winterboum 様
ikedas 様

ご回答、誠にありがとうございます。

「sqrt(num) まで探せば良い」
「numの平方根以下だけを調べていることになりますから」
確かにそうですね、よく見れば平方根以下の数字をチェックしていることにほかなりませんね。

「それまでにわかった素数をしまっておいて、それら全てで割り切れなければ OK 」
「2以外の素数はすべて奇数です。numとしてはrange(3, 100, 2)の範囲を調べればいい」
これも確かにそうですね、気づくことができませんでした。

「組み込み関数divmod()を使うと商と剰余を一度に求められる」
「3よりも大きい素数は必ず 6n±1 (n>=1) 」
「エラトステネスの篩」
これらについては存じ上げませんでした。

現在転職のためのコーディングテストの対策として、今回の質問をさせていただきましたが、テスト対策を考える場合は、テスト中にこれらの事柄を調べられる環境にあるか(ネットを使用できるか)、調べられる場合どのくらいの時間検索に費やし、どのくらいの時間でコードを記述できるかの訓練も必要になりそうですね。

少し話がそれましたが、様々な案をご教示いただき、誠にありがとうございました。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

#7

TakaiY

総合スコア12774

投稿2023/07/22 11:57

プログラムの添削ではなく、違う観点から。

テスト対策を考える場合は、テスト中にこれらの事柄を調べられる環境にあるか

無いと思います。
ということは、これらのことは知っていることが前提です。
今回「素数を書き出すプログラム」が課題であり、それが 「100以下のもの」という条件であれば、エラトステネスの篩を使うのが効率がよいというのは、いわば常識であり、それがテストに出るということは、そのアルゴリズムを知っているかどうかを問うていると思っていいと思います。

そういうアルゴリズムを習得するのであれば、そういうものをまとめた書籍などがあるので、やってみるのがいいでしょう。

ただ、今回の質問のコードは、素数の性質から独自のアルゴリズムを導き出していて、効率は措いても問題解決力はあると思いました。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

#8

saichanian

総合スコア22

投稿2023/07/22 12:24

fourteenlength 様

ご回答、誠にありがとうございます。

「Numbaで@njit()する」
そのようなライブラリがあるのですね。
使う際にはいくつか工夫が必要になる可能性もあるようですので、注意が必要双ではありますが、重い処理等を行う場合には試してみようと思います。

「ミラーラビンテストは普通の人(≒暗号処理を生業にしている人以外)には実用足る精度で素数判定できます」
そのような方法もあるのですね、承知いたしました。
私個人がこの手法を利用するのはなかなか難しそうです。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

#9

saichanian

総合スコア22

投稿2023/07/22 12:52

TakaiY 様

ご回答、誠にありがとうございます。

「無いと思います。」
承知いたしました。
私自身コーディングテストを受けた経験がなかったので、参考になりました。

「エラトステネスの篩を使うのが効率がよいというのは、いわば常識」
常識なのですね!
本日初めて知りました。

最近LeetCodeというサイトにてコーディングテスト対策を行い始めましたが、上記のような事柄が常識となっているのであれば、このサイト等で問題の数をこなしてそのような知識を身に着ける必要がありそうですね。

ご教示いただきありがとうございました。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

#10

退会済みユーザー

退会済みユーザー

総合スコア0

投稿2023/07/22 12:55

raithendさん (#8)

私個人がこの手法を利用するのはなかなか難しそうです。

#5で私が書いた技術メモさんのコードを見てもらえるとわかりますが、エラトステネスの篩のコードが書けるのであればミラーラビンテストのコードもさらさらと書けそうな長さです。

「説明せよ」となると、(もう捨ててしまいましたが)そっち系の本でミラーラビンテストを解説しているページ読んだほうが良いと思います。フェルマーの小定理を使うので(用途的に説明が)うっとおしいですよね。

エラトステネスの篩よりさらに早いので「とにかく早い」(一頭地を抜けてドヤる)のであればミラーラビンテストもありと思います。ただ、早いのには理由があり、制約の「100以下」であれば全く問題ありませんが、カーマイケル数(最小で561)は検知できない弱点があります。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

#11

saichanian

総合スコア22

投稿2023/07/22 13:59

fourteenlength 様

ありがとうございます。
確かにコード量的には、そこまでではありませんね。
理解には少し骨が折れそうですが、、

カーマイケル数(最小で561)が検知できないのは少し問題がありそうですね。

私が今回のプログラムを書く上で問題の参考にしたのが、以下のYouTube動画です(0:38~)。
【エンジニア就活】コーディングテスト対策は早めにやろう。LINE新卒採用コーディングテストを紹介。Web系企業の新卒採用対策ならLeetCodeとAtCoder。競技プログラミング | 競プロ

こちらの動画では、素数かを判定する数がものすごく巨大だった場合にどうするかを考慮しております(1:36~)ので、カーマイケル数を取りこぼしてしまうミラーラビンテストよりはエラトステネスの篩のほうがよさそうですね。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

#12

winterboum

総合スコア23349

投稿2023/07/22 13:59

#10

エラトステネスの篩のコードが書けるのであればミラーラビンテストのコードもさらさらと書けそうな長さ

いやあ〜〜
長さでは確かにそうですが、それには ロジックをサラサラと説明できるくらいでないと。。。 私には無理。
Wiki 見ましたが ???。
Wikiのrubyのcodeを見て なんとなくやり方はわかったかなぁ 程度です。
エラトステネスの篩 は再発明してましたが、それでもこれは難しい。整数学 を学んでないと厳しいでしょう。

余談
Wikiのrubyのcodeを見て 思ったのは、
rubyかよ、それなら
require 'prime'
n.prime?
だろう!

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

#13

winterboum

総合スコア23349

投稿2023/07/22 14:26

編集2023/07/23 14:13

素数の話だということで思わず便乗してしまい反省しています。
このPostを削除・編集してしまうとこれに答えてくださったPostが意味をなさなくなるので、このままとさせてください

便乗質問
素数の定義って「1と自分自身以外に約数を持たない数」以外に見たことが無いのですが、素数判定のプログラム見てると 1 は素数扱いになっていないのが多い。
素数の定義からは素数である と言えるのでは?
素数で無いものを合成数と言うのなら、1は合成数? とてもそうは言えない。

このあたりスッキリした説明って有るのでしょうか。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

#14

退会済みユーザー

退会済みユーザー

総合スコア0

投稿2023/07/22 14:30

編集2023/07/22 14:32

各位

素数かを判定する数がものすごく巨大だった場合にどうするかを考慮しております(1:36~)

ここなんですよね、カーマイケル数は数が大きければ大きいほど発生頻度が低いので、素数生成のための素数判定(メルセンヌツイスタか何かで作った例えば整数2000桁の乱数の荒削り)には事足りると思います。桁が大きければ大きいほど、エラストテネスの篩よりも早い分ミラーラビンテストの価値が高まるわけです。

ただ、いざ暗号化に使うときにミラーラビンテストで済ませると、(確率が低いとはいえカーマイケル数を引いてしまうと)暗号として破綻してしまうので、肝腎要はエラストテネスの篩がいいと思います。

用途(100までしかない)と制約(カーマイケル数は捌けない)、ロジック(フェルマー略)まで説明できるなら採用先も満足するハズです。

ここからは個人的な話です。
私も名前は知ってはいますが、説明せよと言われたら「フェルマーの小定理は複雑ですので、〇〇という文献の〇〇という解説に沿って実装しました。与えられた条件の中では現状最速のアルゴリズムと思われます。(もうやめて、私のHPはゼロよ!)」と切り抜けます💦

回答して以来、プログラムの外側の話で心配事があり追記しました。出題者の意図を汲んで回答する必要がある、という話です。

もし、エラストテネスの篩を模範回答、√nが良回答、n/2がボーダーとして出題者が想定していた場合、間違いなくミラーラビンテストは意見が割れます。

  • 悪く取られるケース

「可読性、協調性重視」の職場であれば、こんなキワモノを出されたら選考で弾かれます。難解すぎて「数式はわかるよ、言いたいこともわかる。こんなコード短すぎてスパゲッティコードより扱いに困るわ」となりかねません。

  • 良く取られるケース

「技術調査能力、何としても世界一を狙う野心重視」の職場であれば一目置かれるハズですし、そういう職場は多分模範回答にミラーラビンテストが入っているハズです。その場合は、「良くやって来たね」と声をかけてもらえるハズです。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

#15

ikedas

総合スコア4337

投稿2023/07/22 14:43

編集2023/07/22 14:48

winterboumさん

「1と自分自身以外に約数を持たない数」というのが素数の定義なので、1が素数であるかどうかはその定義とは関係がない。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

#16

winterboum

総合スコア23349

投稿2023/07/22 14:50

#15
???
1が素数であるかどうか は別の定義なりなにか、があるということですか?

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

#17

Zuishin

総合スコア28660

投稿2023/07/22 15:26

1 は素数でも合成数でもありません。
0 も 0.5 も √2 も違います。

全ての数を素数と合成数に分けることができると考えると違和感が生じるかもしれませんが、素数も合成数も特定の条件を満たす数と考えるとすんなり理解できるのではないかと思います。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

#18

winterboum

総合スコア23349

投稿2023/07/23 00:24

#17
ありがとうございます。
どうも整数学は難しい、、、十分理解できそうにありませんが
このスレッドの流れでは無いのでここで一旦止めさせてください。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

#19

Zuishin

総合スコア28660

投稿2023/07/23 02:36

クエスチョンマークは答えを期待している時に使います。
関係ないところで便乗質問をした上に疑問を続け、返事があると「流れが違う」というのは流石に勝手すぎるでしょう。

定義は調べればすぐにわかることなので、難しいわからないと言うのではなく、自分で調べてください。

これ以上はこの質問に関係ないのでこの話はここで終わりにしてください。
もういいでしょう?

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

#20

winterboum

総合スコア23349

投稿2023/07/23 02:52

#19
「流れが違う」と書きましたのは、
Zuishinさんの言われる「これ以上はこの質問に関係ないのでこの話はここで終わりにしてください。」
という同じ意味合いで使いました。
便乗質問であるのと、私には現状ではすぐには理解しきれそうにないので、このスレッドでは迷惑になるかな、と。
舌足らずで有ったようでご不快にさせてしまったようで申し訳ありません。

で、
「1はなぜ素数扱いにされていないのだ」は以前から気になっていて調べてはいたのですが、「1と自分自身以外に約数を持たない数」以上の定義?説明?に巡り合わせて居なかったので、「このスレッドは整数学に詳しい方が参加されてるみたいだ」ということで質問させていただきました。
#15、#17(の前半)のご回答が理解できず、現状の私の数学力ではだめか、と感じた次第です。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

#21

Zuishin

総合スコア28660

投稿2023/07/23 02:55

いつまで続けるつもりですか?

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

#22

TakaiY

総合スコア12774

投稿2023/07/23 03:16

1が素数であるかどうか

違う話題での投稿すみません。 以降はやりません。

https://ja.wikipedia.org/wiki/%E7%B4%A0%E6%95%B0
Wikipediaの素数のところに「1 は素数か」という項目があります。読んでみるといいと思います。 定義というのは常にきっちり決っているわけではないこともあるということです。
また、今の素数の定義は、「2 以上の自然数で、正の約数が 1 と自分自身のみであるもののこと」とするのが一般的ということと思います。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

#23

winterboum

総合スコア23349

投稿2023/07/23 03:17

#21
この話題は終わります。お騒がせしました。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

#24

saichanian

総合スコア22

投稿2023/07/23 05:23

fourteenlength 様

返信が遅れました。

#14
今後素数判定のプログラムを作成する機会に出会うかはわかりませんが、出会った場合はエラトステネスの篩法とミラーラビンテストの両方を考慮してみようと思います。

しかしながら、コーディングテストの場においては、少なくともミラーラビンテスト手法は使わないような気がしております。
素数判定プログラムは、出題されたとしてもそれにさける時間は10~20分程度ではないかと考えておりますので、ミラーラビンテストをやるほどまでは深堀できないような気がしております。

今後なにか素数判定を用いた開発に携わった場合に、速さを重視するといった場面が訪れれば、検討させていただきたく考えております。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

#25

ikedas

総合スコア4337

投稿2023/07/23 10:27

コーディングテストというのがどんなものか知らないのですが (個人的な事情をいうと、実用ではなく試験のためにコードを書かされたという経験がないのです。歳がばれるな)、採用の方針によっても評価の基準がどのへんにあるのかは違ってくるのだろうと思います。

なんとなく想像ですが、つぎのようなレベル感で考えられそうだと思いました。

a. 単にプログラミングの経験があるかを見て採用後の教育方針に反映させたい。
b. 基本的な文法要素や標準ライブラリについての一通りの知識を持っていることを条件としたい (会社は基礎教育の負担をあまり負いたくない)。
c. 会社が想定する特定のミッションをこなすための知識や経験を持っているか確かめたい。

とりあえず a. はおいておきます。また c. の場合ならどんな技術を求めているかがあらかじめ会社から提示されるはずですから、それに従えばいいと思います。

b. の場合だと、基本的には指示された通りに動作するコードを書けるかどうかの確認になると思われます。たとえば

2^z ≡ 2 (mod z) となる正整数zのうち、最初の100個を表示するプログラムを書きなさい。

なんていう問題が出されるのかと想像したりします。

この場合、Pythonの演算子 (累乗や剰余など) や組み込み関数は、一通り使いこなせる必要があるでしょう。またこの問題ではデータ型として整数型しか現れませんが、ほかの基本データ型や複合的な型、およびそれに対する演算や標準メソッドや制御フローなども同様です。

つまり、Pythonの公式サイトにあるチュートリアルに出てくるような内容は、一通りマスターしていてリファレンスを見返す必要がないようになっていることが理想だと思います。

これに加え、必要に応じて言語リファレンスやライブラリーリファレンスを参照して必要な情報を得る能力も必要と思います (リファレンス類の内容をすべて覚えている必要はないです。必要なのは、調べたいときにどこを調べればいいかわかる能力です)。

ここまでが b. の最低ラインかと思います。

で、Python本体以外にデータ構造やアルゴリズムの知識も、基本的なものは知識として持っているに越したことはないです (ちなみに上の問題はミラー-ラビン法の一部にもなっているフェルマ・テストというもので、高い確率で素数を出力します。素数つながりということで)。

なお、「エラトステネスの篩は常識」といったご意見もありましたが、個別アルゴリズムの知識をどこまで求めてくるかは採用担当者の方針次第かと思います (なんなら担当者に直接聞いてみればいいと思います)。少なくとも、こういったものを実装して動作確認する経験を積んでおくことは、プログラミングの「勘」を養うにはよいと思います。

あと、Pythonに標準で付属している以外の特定のライブラリを何か使いこなせるようになっておくのもよいですね。たとえばNumPyなどという科学計算向けのライブラリがあったりしますが、NumPyではエラトステネスの篩をもっとスマートに書けたりします。試験範囲とは関係なくても、これも経験になります。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

#26

mather

総合スコア6753

投稿2023/07/23 20:32

出題の内容や出題側が何をチェックするのかはわかりませんが、気になった点を1つ。
「素数判定」という言葉を持ち出すときに、「判定をする」というロジックがきちんと関数で切り出されていないのが気になりました。
「2から100の範囲で素数となる数を出力する」という出題であれば今回のような単純な2重ループでも良いと思うのですが、プログラミングの能力を確認するケースではロジックを明確に整理する能力も大事だと思います。

例えば、素数を判定して TrueまたはFalseを返す is_prime 関数を定義できたとして最初のループで行うことはこれだけです。

python

1def is_prime(num): 2 ... 3 4for num in range(2, 100): 5 if is_prime(num): 6 print(num)

こうすることで、 ix のような変数は最初のループの中で使用されていましたが、実際には「素数を判定する」というロジックを実現するために使う補助的な数であって、 次の num を調べるときには引き継ぐ必要がないことがはっきりします。

プログラミングは最初の頃はひとまず動けば良いという面もありますが、プログラミング言語の基礎的な機能を理解し、読み手に対して読みやすく理解しやすいコードを書くことを心がけるのも大事なことだと思います。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

#27

saichanian

総合スコア22

投稿2023/07/24 15:03

ikedas 様

返信遅くなりました。

#25
「b. 基本的な文法要素や標準ライブラリについての一通りの知識を持っていることを条件としたい」
はい、私もだいたいこれくらいの意識でテストを行っているような気がしております。

「Pythonの演算子 (累乗や剰余など) や組み込み関数は、一通り使いこなせる必要がある」
そうですね、私もそのような対策が必要と考えており、組み込み関数やよくメソッドをある程度学習いたしました。
特にリスト型のメソッドは重要である気がしております。
何人かの方に指摘いただいたように、素数判定のプログラムを作成する際にsqrt()関数を利用するといった場合は、mathモジュール等の学習も必要そうですね。

「NumPyなどという科学計算向けのライブラリがあったりします」
ありがとうございます。こちらのご意見を参考にし、NumPyの学習も軽くではありますが、行いました。
特にリストを使用して何かしらの計算を行うようなプログラムを作成する場合には、リストではなくnumpyのarrayを使う方向にシフトしたほうがよさそうな感じはしました。
私が現在目指しているのはWeb系のエンジニアであるので、そこまで込み入った計算を必要とするプログラムの作成はない気がしますが、、、

「こういったものを実装して動作確認する経験を積んでおくことは、プログラミングの「勘」を養うにはよいと思います」
ありがとうございます。コーディングテスト対策サイト等で「勘」を養っておきたいと思います。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

#28

saichanian

総合スコア22

投稿2023/07/25 13:13

mather 様

返信遅くなりました。
#26
「「判定をする」というロジックがきちんと関数で切り出されていないのが気になりました」
ご指摘ありがとうございます。
こちらに関しては、確かにそうかもしれません。
今回の質問では、コード自体は短くできたのではないかと感じておりますが、一方でそれぞれの行で一体どんな操作をしているのか、説明なしに理解していただけるか疑問ではありました。
今回は質問のためにコードの動き方を細かく記述したつもりではありますが、コーディングテストの時にはそんな暇はほとんどないと思いますので、説明をいろいろ書き込まなくとも理解してもらえるよう関数化をするのがポイントだなと、いろいろなコードを書いていく中で確かに思いました。
関数化を行うことで、if文の中にさらにif文を書き込むといったを極力避けるようにしたいと思います。

素数判定の部分を関数化する場合は、下のようなコードになるのでしょうか。
(素数のリスト化も行いました。)

Python

1def isPrimeNumber(num: int, prime_number_list: list[int]) -> bool: 2 for i in prime_number_list: 3 if num % i == 0: 4 return False 5 break 6 else: 7 return True 8 9prime_number_list = [] 10 11for i in range(2, 100): 12 if isPrimeNumber(i, prime_number_list): 13 prime_number_list.append(i) 14 print(i) 15

また、大きな数について素数かどうかを判定する関数も追記します。
(ご指摘いただいたように、約数を見つける範囲をsqrt(num)としております。)

Python

1import math 2 3def isPrimeNumber(num:int): 4 i = 2 5 while i < math.sqrt(num): 6 if num % i == 0: 7 print(num, 'is NOT a prime number.') 8 break 9 else: 10 i += 1 11 else: 12 print(num, 'is a prime number.')

こうしてみると、素数判定を行う関数といっても、小さい順に素数を書き出していくものと、判定を一回のみ行うものとでは、作成の仕方が大きく変わってきますね。
このことは学びになりました。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

#29

ikedas

総合スコア4337

投稿2023/07/26 00:41

編集2023/07/26 00:46

処理単位を関数化することはよいことだと思います。一方で「素数を書き出す」バージョンは、関数化したためにprime_number_listを毎回、関数に引数として与えるという工夫が必要になっています。「素数判定」バージョンで再利用しないのであれば、このような引数は不要なはずです。その場合、グローバル変数にするという方法もあるでしょうが、いずれにしても関数の内部でしか使わない変数が関数の外から見えて操作できる状態ということになります。

このような場合にはジェネレータ関数にすることも考えてよいと思います (詳しくはリンク先のチュートリアルを見てください)。Python以外の言語ではあまり見られない機能ですが、内部状態を保持しながら繰り返し値を返すようなものを作れます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

#30

saichanian

総合スコア22

投稿2023/07/30 06:49

ikedas 様

返信が遅くなってしまい、大変申し訳ございません。
ジェネレータ式の理解に時間がかかってしまいました(といいますか、今でも理解しきれておりません)。

ジェネレータ式の学習にあたって、「みんなのPython 第4版」を使用しておりましたところ、ちょうどジェネレータ式を用いて素数を書き出すプログラムがございましたので、以下に記述いたします。

Python

1def get_primes(x=2): 2 while True: 3 for i in range(2, x): 4 if x % i == 0: 5 break 6 else: 7 yield x 8 x += 1 9 10i = get_primes() 11 12for c in range(10): 13 print(next(i))

柴田淳(2017)『みんなのPython 第4版』P246

このプログラムを、100までの素数を書き出すものに変更するとなると、最後のfor文を以下のようなwhile文にすればよいのでしょうか?

Python

1while next(i) < 100: 2 print(next(i))

ジェネレータ式についてお教えいただき、ありがとうございました。
現状ではまだ理解しきれいていないため、学習を継続していこうと思います。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

#31

ikedas

総合スコア4337

投稿2023/07/30 08:04

『みんなのPython 第4版』では、ジェネレータ関数が返したイテレータを使って順番に素数を取り出す方法を説明しているのですね (わたしは古い第3版しか持っていないのですが、ほぼ同じ説明を確認できました)。

イテレータは最初に全部の素数を返すのではなくnext()が呼ばれるたびにひとつづつ新たな素数を計算して返します (このあたりの仕組みは「クラス」と「メソッド」、「イテレータ」、「ジェネレータ」を学習すれば理解できてきます)。
next(i)を実行するたびに素数がひとつ返ってきますから、おっしゃるような書き方だと素数がひとつおきに出力されることになりますね。

100未満のすべてを出力するには

python

1... 2i = get_primes() 3while True: 4 c = next(i) 5 if c >= 100: 6 break 7 print(c)

あるいは

python

1... 2for c in get_primes(): 3 if c >= 100: 4 break 5 print(c)

などとすればできそうです。後者についてはお持ちの本にも言及があると思いますが、for ... in ...range()のようなシーケンスだけでなくイテレータにも使えて、ループを回るごとにnext()を実行するような動作をします。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

#32

saichanian

総合スコア22

投稿2023/07/30 13:21

ikedas 様

ご意見ありがとうございます。

「おっしゃるような書き方だと素数がひとつおきに出力されることになりますね」
確かに、素数が一つ置きに出力されておりました。
出力の確認ができていなかったのはよくなかったです。
ご指摘ありがとうございます。

また、添付いただいたコードにつきまして、100以下の素数が出力されていることを確認いたしました。
ありがとうございます。

まだまだジェネレータ式についてはよく理解できていないので、学習を継続したいと思います。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

#33

jmdajmw

総合スコア302

投稿2023/07/30 22:51

エラトステネスの篩を使わないと遅いですよ。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

#34

saichanian

総合スコア22

投稿2023/07/31 15:03

編集2023/07/31 15:05

jmdajmw 様

ご意見ありがとうございます。

以下のコードで、実行時間を計測してみました。

Python

1import time

timeモジュールをインポートしたのち、以下の二つのコードを実行してみました。

#31にてikedas様にご教示いただいたコード(について、素数をリスト化したのちprintするよう改良したもの)

Python

1start = time.perf_counter() 2 3def get_primes(x=2): 4 while True: 5 for i in range(2, x): 6 if x % i == 0: 7 break 8 else: 9 yield x 10 x += 1 11 12plist = [] 13 14for c in get_primes(): 15 if c >= 1000: 16 break 17 plist.append(c) 18 19print(plist) 20 21print(time.perf_counter() - start)

実行結果

Python

1[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, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997] 20.006495299999997428

実行時間0.0065秒

エラトステネスの篩法(素数生成プログラム「エラトステネスの篩」を実装|Pythonで数学を学ぼう! 第7回

Python

1start = time.perf_counter() 2 3n = 1000 4p = [i for i in range(n + 1)] 5 6for i in p[3:]: 7 if p[i] % 2 == 0: 8 p[i] = 0 9 10root_n = n ** 0.5 11for i in range(3, n): 12 if i > root_n: 13 break 14 if p[i] != 0: 15 for j in range(i, n + 1, 2): 16 if i * j >= n + 1 : 17 break 18 p[i * j] = 0 19 20plist = sorted(list(set(p)))[2:] 21 22print(plist) 23 24print(time.perf_counter() - start)

実行結果

Python

1[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, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997] 20.0016517000000000337

実行時間0.0017秒

この二つのコードを何度か実行してみましたが、確かにエラトステネスの篩法はジェネレータ関数を用いた方法よりも数分の一程度の実行結果となっておりました。(n=1000の時)

n = 10000の時は、ジェネレータ関数によるものが0.32秒、エラトステネスの篩法が0.0069秒となりましたので、nが非常に大きな数になった場合、エラトステネスの篩法は前者とは比較にならないほど実行時間が短くて済みそうでした。

ご指摘いただき、ありがとうございました。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

#35

otn

総合スコア84574

投稿2023/08/02 01:57

「エラトステネスの篩を使うのが効率がよいというのは、いわば常識」
常識なのですね!

高校数学の範囲かと思っていましたが、ググってもよくわからず。
・高校数学を扱った勉強支援サイトの素数の説明では出てきているが、カリキュラムの中なのか、カリキュラム外の参考知識なのか明記されず
・高校数学カリキュラム一覧のようなサイトではそこまで詳細でなく、よくわからず

全員が学んでいるわけじゃなくて、先生によっては言及すると言うことなのですかね。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

#36

saichanian

総合スコア22

投稿2023/08/02 12:11

otn 様

私も、理系の学部出身ではありますが、初めて知りました。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

#37

otn

総合スコア84574

投稿2023/08/02 12:42

私も、理系の学部出身ではありますが、初めて知りました。

なるほど。忘れてたわけじゃなくて、本当に知らなかったとのことで、
「高校数学の範囲なので常識のはず」と思っていたけど、やっぱり、間違いと言うことですね。

たまに、数学に限らず、「~~~って、中学で習うんだっけ?高校でだっけ?」と思って検索することが時々あるのですが、
検索だけで明確に判明することは少ないです。自分の子供が中高生だったのもずいぶん昔で、教科書見るとかも困難。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

最新の回答から1ヶ月経過したため この意見交換はクローズされました

意見をやりとりしたい話題がある場合は質問してみましょう!

質問する

関連した質問