[解決済み] Python言語用isPrime関数

質問

そこで、インターネットの力を借りて、この問題を解決したところ、このような結果が得られました。

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

しかし、私の質問は、本当にそれを行う方法ですが、なぜです。1が素数であってもquot;prime"とみなされないことは理解していますし、範囲内の何かで割ると自動的に素数ではなくなるのでreturn False文になることも理解しています。しかし私の質問は ここで、"n" の平方根はどのような役割を果たすのでしょうか？ ?

P.s. 私は非常に経験が浅く、1ヶ月前にプログラミングに触れたばかりです。

どのように解決するのですか？

インターネット上にあふれる多くの素数テストの中から、次のPython関数を考えてみましょう。

def is_prime(n):
  if n == 2 or n == 3: return True
  if n < 2 or n%2 == 0: return False
  if n < 9: return True
  if n%3 == 0: return False
  r = int(n**0.5)
  # since all primes > 3 are of the form 6n ± 1
  # start with f=5 (which is prime)
  # and test f, f+2 for being prime
  # then loop by 6. 
  f = 5
  while f <= r:
    print('\t',f)
    if n % f == 0: return False
    if n % (f+2) == 0: return False
    f += 6
  return True    

すべての素数 > 3 以降 は 6n ± 1 の形式であることを排除すると、次のようになります。 n があります。

1. 2でも3でもなく（これらは素数）、かつ
2. 偶数でない n%2 ) と
3. で割り切れない（3 n%3 ) ならば、6番目のn ± 1ごとにテストすればいいのです。

素数5003を考える。

print is_prime(5003)

プリントする。

 5
 11
 17
 23
 29
 35
 41
 47
 53
 59
 65
True

行 r = int(n**0.5) は 70 と評価されます（5003 の平方根は 70.7318881411 であり int() はこの値を切り捨てる)

5005の次の奇数（2以外の偶数は素数ではないので）を考えても、同じことが印刷されます。

 5
False

から平方根が限界です。 x*y == y*x この関数は、5005が5で割り切れるので素数でないことを見つけるために1ループするだけです。ということは 5 X 1001 == 1001 X 5 (そして両方とも5005)、5でわかっていることを1001までループする必要はありません!

では、あなたの持っているアルゴリズムを見てみましょう。

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

    return True

課題は2つあります。

1. をテストしません。 n は2より小さく、2より小さい素数は存在しない。
2. 2からn**0.5までのすべての数（すべての偶数とすべての奇数を含む）をテストします。2で割り切れる2より大きな数はすべて素数ではないので、2より大きな奇数のみをテストすることで少し速度を上げることができます。

だから

def isPrime2(n):
    if n==2 or n==3: return True
    if n%2==0 or n<2: return False
    for i in range(3, int(n**0.5)+1, 2):   # only odd numbers
        if n%i==0:
            return False    

    return True

OK -- これで約30%高速化されました（ベンチマークしてみました...）。

私が使用したアルゴリズム is_prime は、6個目の整数ごとにループを回すだけなので、それでも2倍くらい速いです。 (もう一度、ベンチマークをとってみました)。

余談：x**0.5 は平方根です。

>>> import math
>>> math.sqrt(100)==100**0.5
True

余談2． プライマリーテスト は、コンピュータサイエンスにおける興味深い問題である。