Givet ett positivt heltal N, är uppgiften att skriva ett Python-program för att kontrollera om numret är det främsta eller inte in Pytonorm .

Exempel:

  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 för att kontrollera primtal

Tanken att lösa detta problem är att iterera genom alla siffror från 2 till (N/2) med hjälp av en för slinga och för varje tal kontrollera om det delar N. Om vi ​​hittar något tal som delar, returnerar vi falskt. Om vi ​​inte hittade något tal mellan 2 och N/2 som delar N så betyder det att N är primtal och vi kommer att returnera Sant.

num = 11 # If given number is greater than 1 if num>1: # Iterera från 2 till n // 2 för i i intervallet(2, (num//2)+1): # Om num är delbart med valfritt tal mellan # 2 och n / 2, är det inte primtal om ( num % i) == 0: print(num, 'är inte ett primtal') break else: print(num, 'är ett primtal') else: print(num, 'är inte ett primtal nummer')>

11 is a prime number>

Tidskomplexitet :O(n)
Extra utrymme: O(1)

.tostring java

Hitta primtal med en flaggvariabel

Istället för att kontrollera till n kan vi kontrollera till √n eftersom en större faktor på n måste vara en multipel av en mindre faktor som redan har kontrollerats. Låt oss nu se koden för den första optimeringsmetoden (dvs kontrollera till √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): för i i intervall(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>

Tidskomplexitet :O(sqrt(n))
Extra utrymme: O(1)

Kontrollera primtal med hjälp av rekursion

Vi kan också hitta talet primtal eller inte använda rekursion . Vi kan använda den exakta logiken som visas i metod 2 men på ett rekursivt sätt.

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>

Tidskomplexitet: O(sqrt(n))
Hjälputrymme :O(sqrt(n))

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

Tidskomplexitet: O(sqrt(n))
Hjälputrymme: O(sqrt(n))

Rekommenderad artikel – Analys av olika metoder för att hitta primtal i Python

Python-program för att kontrollera primtal Använda en while-loop för att kontrollera delbarhet

Initiera en variabel i till 2, medan i kvadrat är mindre än eller lika med n, kontrollera om n är delbart med i. Om n är delbart med i, returnera False. Öka annars i med 1. Om slingan avslutas utan att hitta en divisor, returnera True.

mediaöverföring

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>

Tidskomplexitet: O(sqrt(n))
Hjälputrymme: O(1)

Python-program för att kontrollera primtal med hjälp av matematikmodulen

Koden implementerar ett grundläggande tillvägagångssätt för att kontrollera om ett tal är primtal eller inte, genom att korsa alla tal från 2 till sqrt(n)+1 och kontrollera om n är delbart med något av dessa tal.

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>

Tidskomplexitet: O(sqrt(n))
Kodens tidskomplexitet är O(sqrt(n)) eftersom vi korsar alla tal i intervallet 2 till sqrt(n)+1 för att kontrollera om n är delbart med något av dem.

Hjälputrymme: O(1)
Kodens rymdkomplexitet är O(1) eftersom vi bara använder en konstant mängd minne för att lagra ingångsnumret n och loopvariablerna.

Python-program för att kontrollera primtal med metoden sympy.isprime().

I sympy-modulen kan vi testa om ett givet tal n är primtal eller inte med funktionen sympy.isprime(). För n <2⁶⁴svaret är definitivt; större n-värden har en liten sannolikhet att faktiskt vara pseudoprimer.

OBS: Negativa tal (t.ex. -13) anses inte vara primtal.

tcp vs udp

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

Produktion

False True True>

Tidskomplexitet: O(sqrt(n)), där n är inmatningsnumret.
Hjälputrymme: O(1)