Pythonでプライムするかどうか

素数は、暗号化などの多くのアプリケーションで中心的な役割を果たします。そのため、さまざまなアプリケーションでPythonプログラムを使用して素数をチェックする必要があります。素数とは、それ自体以外の要素を持たない数のことです。以下に、与えられた数が素数であるかどうかを調べることができるプログラムを示します。

アプローチ

数が素数であるかどうかを判断するために、次のアプローチを取ります。

• 最初のチェックはポジティブかどうか。正の数だけが素数になることができるので。

• 数値を、指定された数値より2から1少ない数値の範囲内のすべての数値で除算します。

• この範囲のいずれかの数値の余りがゼロになる場合、それは素数ではありません。

例

x = 23
if x > 1:
   for n in range(2, x):
      if (x % n) == 0:
         print(x, "is not prime")
         print(n, "times", x // n, "is", x)
         break
   else:
      print(x, "is a prime number")
   else:
      print(x, "is not prime number")

出力

上記のコードを実行すると、次の結果が得られます-

23 is a prime number

フォーム6i+1の確認

6より大きいすべての素数は、6i+1の形式で表すことができます。ここで私は1から始めて、整数として進みます。以下の例では、6を分割し、リマインダーを1つとしてチェックすることにより、番号を6i+1の形式で表示できるかどうかを確認します。したがって、数が素数であるかどうかを決定します。また、与えられた数の平方根に等しいi値をチェックする必要があります。

例

def CheckPrime(n):
   # Check for cases of 2 and 3
   if (n <= 1):
      return False
   if (n <= 3):
      return True
   # skip checking middle five numbers in the loop
   if (n % 2 == 0 or n % 3 == 0):
      return False
   i = 5
   while (i * i <= n):
      if (n % i == 0 or n % (i + 2) == 0):
         return False
      i = i + 6
   return True
# Check for inputs
if (CheckPrime(31)):
   print(" true")
else:
   print(" false")
if (CheckPrime(25)):
   print(" true")
else:
   print(" false")

出力

上記のコードを実行すると、次の結果が得られます-

true
false