Vzhľadom na kladné celé číslo N je úlohou napísať program v Pythone, aby sme skontrolovali, či je to číslo hlavný alebo nie v Python .

Príklady:

  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, ….}.>

Program Python na kontrolu prvočísla

Myšlienkou na vyriešenie tohto problému je iterovať cez všetky čísla od 2 po (N/2) pomocou a pre slučku a pre každé číslo skontrolujte, či delí N. Ak nájdeme akékoľvek číslo, ktoré delí, vrátime false. Ak sme nenašli žiadne číslo medzi 2 a N/2, ktoré delí N, znamená to, že N je prvočíslo a vrátime True.

num = 11 # If given number is greater than 1 if num>1: # Iteruje od 2 do n // 2 pre i v rozsahu (2, (num//2)+1): # Ak je číslo deliteľné ľubovoľným číslom medzi # 2 a n / 2, nie je prvočíslo, ak ( num % i) == 0: print(num, 'nie je prvočíslo') break else: print(num, 'je prvočíslo') else: print(num, 'nie je prvočíslo číslo')>

11 is a prime number>

Časová zložitosť : O(n)
Pomocný priestor: O(1)

Nájdite prvočísla pomocou premennej príznaku

Namiesto kontroly do n môžeme kontrolovať do √n, pretože väčší faktor n musí byť násobkom menšieho faktora, ktorý už bol skontrolovaný. Teraz sa pozrime na kód prvej metódy optimalizácie (t. j. kontrola do √n)

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): pre i v rozsahu(2, int(sqrt(n)) + 1): if (n % i == 0): prime_flag = 1 zlom if (prime_flag == 0): print('True' ) else: print('False') else: print('False')>

False>

Časová zložitosť :O(sqrt(n))
Pomocný priestor: O(1)

Skontrolujte prvočísla pomocou rekurzie

Môžeme tiež nájsť číslo prvočíslo alebo nepoužívať rekurzia . Môžeme použiť presnú logiku znázornenú v metóde 2, ale rekurzívnym spôsobom.

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))>

True>

Časová zložitosť: O(sqrt(n))
Pomocný priestor :O(sqrt(n))

Skontrolujte metódu primárnej skúšobnej divízie

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>

Časová zložitosť: O(sqrt(n))
Pomocný priestor: O(sqrt(n))

Odporúčané Artilce – Analýza rôznych metód na nájdenie prvočísla v Pythone

Program Python na kontrolu prvočísla Pomocou cyklu while na kontrolu deliteľnosti

Inicializujte premennú i na 2, zatiaľ čo i na druhú je menšie alebo rovné n, skontrolujte, či je n deliteľné i. Ak je n deliteľné i, vráti hodnotu False. V opačnom prípade zvýšte hodnotu i o 1. Ak cyklus skončí bez nájdenia deliteľa, vráťte hodnotu True.

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>

Časová zložitosť: O(sqrt(n))
Pomocný priestor: O(1)

Program Python na kontrolu prvočísla pomocou matematického modulu

Kód implementuje základný prístup na kontrolu, či je číslo prvočíslo alebo nie, prechodom cez všetky čísla od 2 do sqrt(n)+1 a kontrolou, či je n deliteľné ktorýmkoľvek z týchto čísel.

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>

Časová zložitosť: O(sqrt(n))
Časová zložitosť kódu je O(sqrt(n)), pretože prechádzame všetkými číslami v rozsahu 2 až sqrt(n)+1, aby sme skontrolovali, či je n deliteľné niektorým z nich.

Pomocný priestor: O(1)
Priestorová zložitosť kódu je O(1), pretože na uloženie vstupného čísla n a premenných cyklu používame iba konštantné množstvo pamäte.

Program Python na kontrolu prvočísla pomocou metódy sympy.isprime().

V module sympy môžeme pomocou funkcie sympy.isprime() otestovať, či je dané číslo n prvočíslo alebo nie. Pre n <2⁶⁴odpoveď je definitívna; väčšie hodnoty n majú malú pravdepodobnosť, že sú v skutočnosti pseudoprimé.

Pozn.: Záporné čísla (napr. -13) sa nepovažujú za prvočíslo.

# 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>

Výkon

False True True>

Časová zložitosť: O(sqrt(n)), kde n je vstupné číslo.
Pomocný priestor: O(1)