Pythonプログラムで素数を見つけるためのさまざまな方法の分析

このチュートリアルでは、すべてのメソッドに必要な素数と時間を見つけるためのさまざまなメソッドを見ていきます。時間モジュールを使用して実行時間を計算します。

方法-1

素数を見つける一般的な方法です。

• 数値が1以下の場合は、Falseを返します。
• 数値が任意の数値で割り切れる場合、関数はFalseを返します。
• ループの後、Trueを返します。

例

# importing time module
import time
# checking for prime
def is_prime(n):
   if n <= 1:
      return False
   else:
      for i in range(2, n):
         # checking for factor
         if n % i == 0:
            # return False
            return False
      # returning True
      return True
# starting time
start_time = time.time()
primes = 0
for i in range(100000):
   if is_prime(i):
      primes += 1
print(f'Total primes in the range {primes}')
# ending time
end_time = time.time()
print(f'Execution time: {end_time - start_time}')

出力

上記のプログラムを実行すると、次の結果が得られます。

Total primes in the range 9594
Execution time: 63.1301212310791

方法-2

この方法では、nの平方根にカットすることで、反復回数を減らしています。

コードを見てみましょう。

例

# importing time module
import time
# importing math module for sqrt function
import math
# checking for prime
def is_prime(n):
   if n <= 1:
      return False
   else:
      # iterating loop till square root of n
      for i in range(2, int(math.sqrt(n)) + 1):
         # checking for factor
         if n % i == 0:
            # return False
            return False
      # returning True
      return True
# starting time
start_time = time.time()
primes = 0
for i in range(100000):
   if is_prime(i):
      primes += 1
print(f'Total primes in the range {primes}')
# ending time
end_time = time.time()
print(f'Execution time: {end_time - start_time}')

出力

上記のプログラムを実行すると、次の結果が得られます。

Total primes in the range 9592
Execution time: 0.2039644718170166

方法-3

前の方法では、偶数をチェックしました。 2つを除いて、偶数は素数になり得ないことは誰もが知っています。 。したがって、この方法では、時間を短縮するためにすべての偶数を削除します。

例

# importing time module
import time
# importing math module for sqrt function
import math
# checking for prime
def is_prime(n):
   # checking for less than 1
   if n <= 1:
      return False
   # checking for 2
   elif n == 2:
      return True
   elif n > 2 and n % 2 == 0:
      return False
   else:
      # iterating loop till square root of n
      for i in range(3, int(math.sqrt(n)) + 1, 2):
         # checking for factor
         if n % i == 0:
            # return False
            return False
      # returning True
      return True
# starting time
start_time = time.time()
primes = 0
for i in range(100000):
   if is_prime(i):
      primes += 1
print(f'Total primes in the range {primes}')
# ending time
end_time = time.time()
print(f'Execution time: {end_time - start_time}')

出力

上記のプログラムを実行すると、次の結果が得られます。

Total primes in the range 9592
Execution time: 0.10342741012573242

結論

チュートリアルについて疑問がある場合は、コメントセクションにその旨を記載してください。