正の整数 N が与えられた場合、その数値が次の値であるかどうかを確認する Python プログラムを作成することがタスクです。 プライム または入っていない パイソン 。
例:
Input: n = 11 Output: True Input: n = 1 Output: False Explanation: A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. The first few prime numbers are {2, 3, 5, 7, 11, ….}.>素数を確認するための Python プログラム
この問題を解決するアイデアは、次の関数を使用して 2 から (N/2) までのすべての数値を反復処理することです。 for ループ そして、すべての数値について、N を割るかどうかを確認します。割れる数値が見つかった場合は、false を返します。 2 と N/2 の間に N を割る数値が見つからなかった場合は、N が素数であることを意味し、True を返します。
Python3 num = 11 # If given number is greater than 1 if num>1: # 2 から n まで反復します // 2 for i in range(2, (num//2)+1): # num が # 2 と n / 2 の間の任意の数で割り切れる場合、それは素数ではありません if ( num % i) == 0: print(num, 'は素数ではありません') Break else: print(num, 'は素数です') else: print(num, 'は素数ではありません番号')>>
出力
11 is a prime number>
時間計算量 ： の上）
補助スペース: ○(1)
フラグ変数を使用して素数を検索する
n までチェックする代わりに、√n までチェックすることができます。これは、n の大きい係数は、すでにチェックされている小さい係数の倍数でなければならないためです。次に、最初の最適化方法 (つまり、 √n までチェックする) のコードを見てみましょう。
Python3
from math import sqrt # n is the number to be check whether it is prime or not n = 1 # this flag maintains status whether the n is prime or not prime_flag = 0 if(n>1): for i in range(2, int(sqrt(n)) + 1): if (n % i == 0): prime_flag = 1 Break if (prime_flag == 0): print('True' ) else: print('False') else: print('False')>>'
出力 False>
時間計算量 :O(sqrt(n))
補助スペース: ○(1)
再帰を使用して素数を確認する
素数または素数を使用しないことも見つけることができます 再帰 。方法 2 で示したロジックを再帰的に使用することができます。
Python3 from math import sqrt def Prime(number,itr): #prime function to check given number prime or not if itr == 1: #base condition return True if number % itr == 0: #if given number divided by itr or not return False if Prime(number,itr-1) == False: #Recursive function Call return False return True num = 13 itr = int(sqrt(num)+1) print(Prime(num,itr))>
出力
補助スペース :O(sqrt(n))
第一審の分割方法を確認する
Python3 def is_prime_trial_division(n): # Check if the number is less than # or equal to 1, return False if it is if n <= 1: return False # Loop through all numbers from 2 to # the square root of n (rounded down to the nearest integer) for i in range(2, int(n**0.5)+1): # If n is divisible by any of these numbers, return False if n % i == 0: return False # If n is not divisible by any of these numbers, return True return True # Test the function with n = 11 print(is_prime_trial_division(11))>
出力
True>
時間計算量: O(sqrt(n))
補助スペース: O(sqrt(n))
おすすめの記事 – Python で素数を見つけるさまざまな方法の分析
素数をチェックする Python プログラム while ループを使用して割り切れ性をチェックする
変数 i を 2 に初期化します。i の 2 乗が n 以下である間、n が i で割り切れるかどうかを確認します。 n が i で割り切れる場合は、False を返します。それ以外の場合は、i を 1 ずつインクリメントします。除数が見つからないままループが終了した場合は、True を返します。
Python3 import math def is_prime(n): if n < 2: return False i = 2 while i*i <= n: if n % i == 0: return False i += 1 return True print(is_prime(11)) # True print(is_prime(1)) # False>
出力
True False>
時間計算量: O(sqrt(n))
補助スペース: O(1)
数学モジュールを使用して素数をチェックする Python プログラム
このコードは、2 から sqrt(n)+1 までのすべての数値を調べ、n がそれらの数値のいずれかで割り切れるかどうかをチェックすることにより、数値が素数かどうかをチェックする基本的なアプローチを実装しています。
Python3 import math def is_prime(n): if n <= 1: return False for i in range(2, int(math.sqrt(n)) + 1): if n % i == 0: return False return True n = 11 print(is_prime(n))>
出力
True>
時間計算量: O(sqrt(n))
コードの時間計算量は O(sqrt(n)) です。これは、2 から sqrt(n)+1 の範囲内のすべての数値を調べて、n がそれらのいずれかで割り切れるかどうかを確認するためです。
補助スペース: ○(1)
入力数値 n とループ変数を格納するために一定量のメモリのみを使用しているため、コードの空間複雑度は O(1) です。
sympy.isprime() メソッドを使用して素数を確認する Python プログラム
sympy モジュールでは、sympy.isprime() 関数を使用して、指定された数値 n が素数であるかどうかをテストできます。 n<2の場合64答えは決定的です。 n の値が大きいほど、実際に擬似素数である可能性は低くなります。
3か月ぶり
Python3注意： 負の数 (-13 など) は素数とみなされません。
# Python program to check prime number # using sympy.isprime() method # importing sympy module from sympy import * # calling isprime function on different numbers geek1 = isprime(30) geek2 = isprime(13) geek3 = isprime(2) print(geek1) # check for 30 is prime or not print(geek2) # check for 13 is prime or not print(geek3) # check for 2 is prime or not # This code is contributed by Susobhan Akhuli>
出力
False True True>
時間計算量: O(sqrt(n))、n は入力数値です。
補助スペース: ○(1)