Če je dano pozitivno celo število N, je naloga napisati program Python, da preveri, ali je število Prime ali ne v Python .

Primeri:

  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 za preverjanje praštevil

Zamisel za rešitev tega problema je ponavljanje vseh števil, ki se začnejo od 2 do (N/2) z uporabo za zanko in za vsako število preverimo, ali deli N. Če najdemo katero koli število, ki deli, vrnemo false. Če nismo našli nobenega števila med 2 in N/2, ki deli N, to pomeni, da je N praštevilo in bomo vrnili True.

num = 11 # If given number is greater than 1 if num>1: # Ponavljanje od 2 do n // 2 za i v obsegu(2, (num//2)+1): # Če je num deljivo s poljubnim številom med # 2 in n / 2, ni praštevilo, če ( num % i) == 0: print(num, 'ni praštevilo') break else: print(num, 'je praštevilo') else: print(num, 'ni praštevilo') številka')>

11 is a prime number>

Časovna zapletenost : O(n)
Pomožni prostor: O(1)

polje s seznamom java

Poiščite praštevila s spremenljivko zastavice

Namesto preverjanja do n lahko preverimo do √n, ker mora biti večji faktor n večkratnik manjšega faktorja, ki je bil že preverjen. Zdaj pa poglejmo kodo za prvo metodo optimizacije (tj. preverjanje 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): 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>

Časovna zapletenost :O(sqrt(n))
Pomožni prostor: O(1)

Preverite praštevila z rekurzijo

Najdemo lahko tudi praštevilo ali neuporabo rekurzija . Uporabimo lahko natančno logiko, prikazano v metodi 2, vendar na rekurziven način.

sistemsko programsko opremo

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>

Časovna zahtevnost: O(sqrt(n))
Pomožni prostor :O(sqrt(n))

Preverite metodo glavne poskusne delitve

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>

Časovna kompleksnost: O(sqrt(n))
Pomožni prostor: O(sqrt(n))

Priporočen članek – Analiza različnih metod za iskanje praštevil v Pythonu

Program Python za preverjanje praštevil Uporaba zanke while za preverjanje deljivosti

Inicializirajte spremenljivko i na 2, medtem ko je i na kvadrat manjši ali enak n, preverite, ali je n deljiv z i. Če je n deljiv z i, vrni False. V nasprotnem primeru povečajte i za 1. Če se zanka konča, ne da bi našli delitelj, vrnite True.

tretja normalna oblika

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>

Časovna zapletenost: O(sqrt(n))
Pomožni prostor: O(1)

Program Python za preverjanje praštevil z uporabo modula Math

Koda izvaja osnovni pristop za preverjanje, ali je število praštevilo ali ne, tako da prečka vsa števila od 2 do sqrt(n)+1 in preveri, ali je n deljivo s katerim koli od teh števil.

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>

Časovna zahtevnost: O(sqrt(n))
Časovna zapletenost kode je O(sqrt(n)), ker prečkamo vsa števila v območju od 2 do sqrt(n)+1, da preverimo, ali je n deljivo s katerim od njih.

Pomožni prostor: O(1)
Prostorska kompleksnost kode je O(1), ker uporabljamo samo konstantno količino pomnilnika za shranjevanje vhodnega števila n in spremenljivk zanke.

Program Python za preverjanje praštevil z uporabo metode sympy.isprime().

V modulu sympy lahko s funkcijo sympy.isprime() preizkusimo, ali je dano število n praštevilo ali ne. Za n <2⁶⁴odgovor je dokončen; večje vrednosti n imajo majhno verjetnost, da bodo dejansko psevdopraštevila.

python inicializacijski seznam

Opomba: Negativna števila (npr. -13) se ne štejejo za praštevila.

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

Izhod

False True True>

Časovna zapletenost: O(sqrt(n)), kjer je n vhodno število.
Pomožni prostor: O(1)