Дано натуральне число N. Завдання полягає в тому, щоб написати програму на Python, щоб перевірити, чи відповідає число Прем'єр або не в Python .

приклади:

  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 для перевірки простих чисел

Ідея вирішення цієї проблеми полягає в тому, щоб перебрати всі числа, починаючи від 2 до (N/2), використовуючи для циклу і для кожного числа перевірте, чи воно ділить N. Якщо ми знайдемо будь-яке число, яке ділить, ми повертаємо false. Якщо ми не знайшли жодного числа між 2 і N/2, яке ділить N, це означає, що N є простим і ми повернемо True.

num = 11 # If given number is greater than 1 if num>1: # Ітерація від 2 до n // 2 для i в діапазоні (2, (num//2)+1): # Якщо num ділиться на будь-яке число від # 2 до n / 2, воно не є простим, якщо ( num % i) == 0: print(num, 'не є простим числом') break else: print(num, 'є простим числом') else: print(num, 'не є простим числом') номер')>

11 is a prime number>

Часова складність : O(n)
Допоміжні приміщення: О(1)

Знайдіть прості числа за допомогою змінної прапора

Замість перевірки до n ми можемо перевірити до √n, оскільки більший множник n має бути кратним меншому множнику, який уже перевірено. Тепер давайте подивимося код для першого методу оптимізації (тобто перевірка до √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>

Часова складність :O(sqrt(n))
Допоміжні приміщення: О(1)

Перевірте прості числа за допомогою рекурсії

Ми також можемо знайти просте число або не використовуючи рекурсія . Ми можемо використовувати точну логіку, показану в методі 2, але рекурсивно.

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>

Часова складність: O(sqrt(n))
Допоміжне приміщення :O(sqrt(n))

завантажити відео з youtube за допомогою vlc

Перевірте метод основного пробного розподілу

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>

Часова складність: O(sqrt(n))
Допоміжний простір: O(sqrt(n))

Рекомендована стаття – Аналіз різних методів пошуку простого числа в Python

Програма Python для перевірки простого числа. Використання циклу while для перевірки подільності

Ініціалізуйте змінну i значенням 2. Хоча i у квадраті менше або дорівнює n, перевірте, чи n ділиться на i. Якщо n ділиться на i, повертає False. В іншому випадку збільште i на 1. Якщо цикл закінчується без знаходження дільника, поверніть 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>

Часова складність: O(sqrt(n))
Допоміжний простір: O(1)

Програма Python для перевірки простих чисел за допомогою модуля Math

У коді реалізовано базовий підхід для перевірки того, чи є число простим чи ні, обходячи всі числа від 2 до sqrt(n)+1 і перевіряючи, чи n ділиться на будь-яке з цих чисел.

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>

Часова складність: O(sqrt(n))
Часова складність коду становить O(sqrt(n)), оскільки ми обходимо всі числа в діапазоні від 2 до sqrt(n)+1, щоб перевірити, чи ділиться n на будь-яке з них.

Допоміжний простір: О(1)
Просторова складність коду становить O(1), оскільки ми використовуємо лише постійний обсяг пам’яті для зберігання вхідного числа n і змінних циклу.

Програма Python для перевірки простого числа за допомогою методу sympy.isprime().

У модулі sympy ми можемо перевірити, чи дане число n є простим чи ні, використовуючи функцію sympy.isprime(). Для n <2⁶⁴відповідь остаточна; більші значення n мають невелику ймовірність бути псевдопростими.

N.B.: Від’ємні числа (наприклад, -13) не вважаються простими числами.

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

Вихід

False True True>

Часова складність: O(sqrt(n)), де n – вхідне число.
Допоміжний простір: О(1)