Gitt et positivt heltall N, er oppgaven å skrive et Python-program for å sjekke om tallet er Prime eller ikke inne Python .

Eksempler:

  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-program for å sjekke primtall

Ideen for å løse dette problemet er å iterere gjennom alle tallene fra 2 til (N/2) ved å bruke en for løkke og for hvert tall sjekk om det deler N. Hvis vi finner et tall som deler, returnerer vi usann. Hvis vi ikke fant noe tall mellom 2 og N/2 som deler N, betyr det at N er primtall og vi vil returnere Sant.

num = 11 # If given number is greater than 1 if num>1: # Iterer fra 2 til n // 2 for i i området(2, (num//2)+1): # Hvis num er delelig med et hvilket som helst tall mellom # 2 og n / 2, er det ikke primtall hvis ( num % i) == 0: print(num, 'er ikke et primtall') break else: print(num, 'er et primtall') else: print(num, 'er ikke et primtall') nummer')>

11 is a prime number>

Tidskompleksitet : O(n)
Ekstra plass: O(1)

Finn primtall med en flaggvariabel

I stedet for å sjekke til n, kan vi sjekke til √n fordi en større faktor på n må være et multiplum av en mindre faktor som allerede er kontrollert. La oss nå se koden for den første optimaliseringsmetoden (dvs. sjekke til √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>

Tidskompleksitet :O(sqrt(n))
Ekstra plass: O(1)

Sjekk primtall ved hjelp av rekursjon

Vi kan også finne tallet primtall eller ikke bruke rekursjon . Vi kan bruke den eksakte logikken vist i metode 2, men på en rekursiv måte.

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>

Tidskompleksitet: O(sqrt(n))
Hjelpeplass :O(sqrt(n))

Sjekk Prime Trial Division Method

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>

Tidskompleksitet: O(sqrt(n))
Hjelpeområde: O(sqrt(n))

Anbefalt artikkel – Analyse av ulike metoder for å finne primtall i Python

Python-program for å sjekke primtall Bruke en while-løkke for å sjekke delbarhet

Initialiser en variabel i til 2, mens i kvadrat er mindre enn eller lik n, sjekk om n er delelig med i. Hvis n er delelig med i, returner False. Ellers øker du i med 1. Hvis sløyfen avsluttes uten å finne en divisor, returner 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>

Tidskompleksitet: O(sqrt(n))
Hjelpeområde: O(1)

gjør mens java

Python-program for å sjekke primtall ved hjelp av matematikkmodul

Koden implementerer en grunnleggende tilnærming for å sjekke om et tall er primtall eller ikke, ved å krysse alle tallene fra 2 til sqrt(n)+1 og sjekke om n er delelig med noen av disse tallene.

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>

Tidskompleksitet: O(sqrt(n))
Tidskompleksiteten til koden er O(sqrt(n)) fordi vi krysser alle tall i området 2 til sqrt(n)+1 for å sjekke om n er delelig med noen av dem.

Hjelpeplass: O(1)
Romkompleksiteten til koden er O(1) fordi vi bare bruker en konstant mengde minne for å lagre inngangsnummeret n og løkkevariablene.

Python-program for å sjekke primtall ved å bruke sympy.isprime()-metoden

I sympy-modulen kan vi teste om et gitt tall n er primtall eller ikke ved å bruke funksjonen sympy.isprime(). For n <2⁶⁴svaret er definitivt; større n-verdier har en liten sannsynlighet for faktisk å være pseudoprimer.

NB: Negative tall (f.eks. -13) regnes ikke som primtall.

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

Produksjon

False True True>

Tidskompleksitet: O(sqrt(n)), der n er inndatanummeret.
Hjelpeplass: O(1)