Python で素数判定プログラムを作る

Question

前提・実現したいこと

素数判定プログラムを作る

Python で素数判定プログラムを以下のように作りました。

発生している問題・エラーメッセージ

9や21,49は素数でないのにもかかわらず、True と表示されてしまいます。
いろいろ調べてみましたが、どこに問題があるのかわかりません。
改善すべきところを教えてください。

また、この is_prime 関数を用いて、n 以下の素数を数えるプログラムはどうやればいいでしょうか。
合わせて教えていただけると幸いです。

該当のソースコード

def is_prime(n)：
if n == 1:
return False
if n == 2:
return True
for k in range(2, int((n ** 0.5)+ 1)):
if n % k == 0:
return False
else:
return True

Comments

[y_waiwai]

このままではコードが読めないので、質問を編集し、<code>ボタンを押し、出てくる’’’の枠の中にコードを貼り付けてください

Answer 1

試し割法ですね。
一度 n % k == 0 が成立しなかったからと言って、素数であると断定するのは尚早です。

return True は試し割が終わった後、for文の外側に置いて下さい。

Comments

[nr5tm]

ありがとうございます。解決しました

Answer 2

再起処理で実装しないと無理かと。
というかfor文が一回回った時点で処理が終了しています。どこが悪いかとかそういうレベルではありません。すべて悪いです。

Comments

[LouiS0616]

素数を再帰処理で判定するコードってあんまり見ないですけど、例えばどんなのがありますか？

[nr5tm]

ありがとうございます。もっと勉強します。

[774]

https://qiita.com/isso_w/items/8982d093760240330ebc
これは配列でその中のってやつです。
自分が考えていたのは入力した数の平方根を上限とした配列を作り、それを多重でって考えていましたが、判定するだけなら確かに試し割りが良さそうですね。重ねて申し訳ありません、
というか試し割法なんてあるんですか。

[LouiS0616]

@774 さん
エラトステネスの篩も非再帰で実装している例の方が多いと思いますよ。
https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Pseudocode

例えば分割統治法のアルゴリズムは再帰と親和性が高いですが（クイックソートなど）、
それでも再帰処理を使わないと書けないわけではありません。

[774]

配列で作るならで思いついたのがその方法であって、後にコード見て再帰で良いんじゃね？ってなった感じです。

再帰じゃないと書けないのはおっしゃる通りですが…そうですね、初心者なのは分かるんですけどそもそもこのプログラムPythonのプログラムなのにインデントが整ってないんですよ。
よくそれで質問したなってので腹立って書きました。発言に勘違いがあったのは申し訳ないです。

[LouiS0616]

コードブロックを使わないとインデントが潰れるので、おそらく質問者の手元では少なくとも文法エラーが出ないレベルにはインデントが付けられている筈です。
本当にインデント無しで実行したらSyntaxErrorで落ちます。

[774]

これっておそらくですが学校の宿題かなんかをこっちで丸投げしてるんじゃないですか？
だからこそおかしい点に気付かずそのまま投げてきたのでは？

それは仮定が間違っているかと。

[774]

まぁでもインデントコードブロックじゃないとつかないのか…

[LouiS0616]

> 9や21,49は素数でないのにもかかわらず、True と表示されてしまいます。

と書いてあるのが丸々嘘で無い限り、インデントが本来付いていると考えるのは充分推論として成立していると思います。
逆に『学校の宿題の丸投げ』というのは、あり得ないとは言いませんが、現時点では「まあそういうふうに想像もできるよね」くらいの説得力しかありません。

[774]

ですか。

[774]

そうだとしても、あのコードは気持ち悪かったです。
まぁだからって言い過ぎか、発言が過激だったのは申し訳ありません。

Answer 3

3 つの方法を書いてみました。
p.py

import math

def is_prime(n):
  if n < 2:
    return False
  if n == 2:
    return True

  for k in range(2, int(math.sqrt(n) + 1)):  
    if n % k == 0:
      return False
  return True

def is_prime_2(n):
  return not (n < 2 or any(n % x == 0 for x in range(2, int(n ** 0.5) + 1)))

def primes_upto(limit):
  is_prime = [False] * 2 + [True] * (limit - 1) 
  for n in range(int(limit**0.5 + 1.5)): # stop at ``sqrt(limit)``
    if is_prime[n]:
      for i in range(n*n, limit+1, n):
        is_prime[i] = False
  return [i for i, prime in enumerate(is_prime) if prime]

MAX = 100
for x in range(1, MAX + 1):
  if is_prime(x):
    print(x, end=" ")
print("")

for x in range(1, MAX + 1):
  if is_prime_2(x):
    print(x, end=" ")
print("")

for x in primes_upto(MAX):
   print(x, end=" ")
print("")

実行例：

参考情報；

• Primality by trial division

https://rosettacode.org/wiki/Primality_by_trial_division#Python

• Sieve of Eratosthenes

https://rosettacode.org/wiki/Sieve_of_Eratosthenes#Python

• 素数の一覧

https://ja.wikipedia.org/wiki/%E7%B4%A0%E6%95%B0%E3%81%AE%E4%B8%80%E8%A6%A7

Answer 4

• 関数定義の末尾の「:」が全角で書いてある
• 試し割は、すべてのkについて割り切れなかったときだけTrue、ひとつでも割り切れる値があればFalse

def is_prime(n):
    if n == 1:
        return False
    if n == 2:
        return True
    for k in range(2, int((n ** 0.5) + 1)):
        if n % k == 0:
            return False
    return True


for i in range(1, 20):
    if (is_prime(i)):
        print(i, end=", ")
print()

2, 3, 5, 7, 11, 13, 17, 19,