Mając dodatnią liczbę całkowitą N, zadaniem jest napisanie programu w Pythonie, który sprawdzi, czy liczba ta jest główny albo nie Pyton .

Przykłady:

  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 w Pythonie do sprawdzania liczby pierwszej

Pomysł rozwiązania tego problemu polega na iteracji po wszystkich liczbach, zaczynając od 2 do (N/2) za pomocą a dla pętli i dla każdej liczby sprawdź, czy dzieli N. Jeśli znajdziemy liczbę, która dzieli, zwracamy wartość false. Jeśli nie znaleźliśmy żadnej liczby pomiędzy 2 i N/2, która dzieli N, oznacza to, że N jest liczbą pierwszą i zwrócimy True.

num = 11 # If given number is greater than 1 if num>1: # Iteruj od 2 do n // 2 dla i w zakresie(2, (num//2)+1): # Jeśli liczba jest podzielna przez dowolną liczbę od # 2 do n / 2, nie jest liczbą pierwszą, jeśli ( num % i) == 0: print(num, 'nie jest liczbą pierwszą') break else: print(num, 'jest liczbą pierwszą') else: print(num, 'nie jest liczbą pierwszą numer')>

11 is a prime number>

Złożoność czasowa : NA)
Przestrzeń pomocnicza: O(1)

Znajdź liczby pierwsze ze zmienną flagową

Zamiast sprawdzać do n, możemy sprawdzić do √n, ponieważ większy współczynnik n musi być wielokrotnością mniejszego czynnika, który został już sprawdzony. Zobaczmy teraz kod pierwszej metody optymalizacji (tj. sprawdzania 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): dla i w zakresie(2, int(sqrt(n)) + 1): if (n % i == 0): prime_flag = 1 przerwa if (prime_flag == 0): print('True' ) else: print('False') else: print('False')>

False>

Złożoność czasowa :O(sqrt(n))
Przestrzeń pomocnicza: O(1)

Sprawdź liczby pierwsze za pomocą rekurencji

Możemy również znaleźć liczbę pierwszą lub nieużywaną rekurencja . Możemy użyć dokładnej logiki pokazanej w metodzie 2, ale w sposób rekurencyjny.

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>

Złożoność czasowa: O(kwadrat(n))
Przestrzeń pomocnicza :O(sqrt(n))

Sprawdź metodę Prime Trial Division

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>

Złożoność czasowa: O(sqrt(n))
Przestrzeń pomocnicza: O(sqrt(n))

Polecany Artilce – Analiza różnych metod znajdowania liczby pierwszej w Pythonie

Program w Pythonie do sprawdzania liczby pierwszej Użycie pętli while do sprawdzenia podzielności

Zainicjuj zmienną i na 2. Chociaż i kwadrat jest mniejsze lub równe n, sprawdź, czy n jest podzielne przez i. Jeśli n jest podzielne przez i, zwróć wartość False. W przeciwnym razie zwiększ i o 1. Jeśli pętla zakończy się bez znalezienia dzielnika, zwróć wartość 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>

Złożoność czasowa: O(sqrt(n))
Przestrzeń pomocnicza: O(1)

Program w Pythonie do sprawdzania liczby pierwszej za pomocą modułu matematycznego

Kod implementuje podstawowe podejście do sprawdzania, czy liczba jest pierwsza, czy nie, poprzez przejście wszystkich liczb od 2 do sqrt(n)+1 i sprawdzenie, czy n jest podzielne przez którąkolwiek z tych liczb.

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>

Złożoność czasowa: O(kwadrat(n))
Złożoność czasowa kodu wynosi O(sqrt(n)), ponieważ przechodzimy przez wszystkie liczby z zakresu od 2 do sqrt(n)+1, aby sprawdzić, czy n jest podzielne przez którąkolwiek z nich.

Przestrzeń pomocnicza: O(1)
Złożoność przestrzenna kodu wynosi O(1), ponieważ używamy tylko stałej ilości pamięci do przechowywania liczby wejściowej n i zmiennych pętli.

Program w Pythonie do sprawdzania liczby pierwszej przy użyciu metody sympy.isprime().

W module sympy możemy sprawdzić, czy dana liczba n jest liczbą pierwszą, czy nie, korzystając z funkcji sympy.isprime(). Dla n <2⁶⁴odpowiedź jest ostateczna; większe n wartości mają małe prawdopodobieństwo, że faktycznie będą liczbami pseudopierwszymi.

Uwaga: Liczby ujemne (np. -13) nie są uważane za liczby pierwsze.

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

Wyjście

False True True>

Złożoność czasowa: O(sqrt(n)), gdzie n jest liczbą wejściową.
Przestrzeń pomocnicza: O(1)