양의 정수 N이 주어지면, 작업은 숫자가 다음과 같은지 확인하는 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)까지 모든 숫자를 반복하는 것입니다. for 루프 모든 숫자에 대해 N을 나누는지 확인합니다. 나누는 숫자를 찾으면 false를 반환합니다. N을 나누는 2와 N/2 사이의 숫자를 찾지 못했다면 이는 N이 소수임을 의미하며 True를 반환합니다.
파이썬3 num = 11 # If given number is greater than 1 if num>1: # 2에서 n까지 반복 // 2 for i in range(2, (num//2)+1): # num이 # 2와 n / 2 사이의 숫자로 나누어지면 소수가 아닙니다. if ( num % i) == 0: print(num, '소수가 아닙니다') break else: print(num, '소수입니다') else: print(num, '소수가 아닙니다') 번호')>
산출
11 is a prime number>
시간 복잡도 : 에)
보조 공간: 오(1)
osi 모델 레이어
플래그 변수를 사용하여 소수 찾기
n까지 확인하는 대신 √n까지 확인할 수 있습니다. n의 더 큰 인수는 이미 확인된 작은 인수의 배수여야 하기 때문입니다. 이제 첫 번째 최적화 방법(예: √n까지 확인)에 대한 코드를 살펴보겠습니다.
파이썬3
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: 인쇄('False') else: 인쇄('False')> 산출
False>
시간 복잡도 :O(sqrt(n))
보조 공간: 오(1)
재귀를 사용하여 소수 확인
우리는 또한 소수를 찾을 수도 있고 사용하지 않을 수도 있습니다. 재귀 . 방법 2에 표시된 정확한 논리를 재귀적인 방식으로 사용할 수 있습니다.
파이썬3 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(제곱(n))
보조 공간 :O(sqrt(n))
프라임 트라이얼 분할 방식을 확인하세요
파이썬3 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를 반환합니다.
C 코드 문자열 배열파이썬3
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 프로그램
코드는 2부터 sqrt(n)+1까지의 모든 숫자를 탐색하고 n이 해당 숫자 중 하나로 나누어지는지 확인하여 숫자가 소수인지 여부를 확인하는 기본 접근 방식을 구현합니다.
파이썬3 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(제곱(n))
코드의 시간 복잡도는 O(sqrt(n))입니다. 왜냐하면 n이 그 중 하나로 나누어지는지 확인하기 위해 2 범위의 모든 숫자를 sqrt(n)+1까지 순회하기 때문입니다.
보조 공간: 오(1)
입력 숫자 n과 루프 변수를 저장하기 위해 일정한 양의 메모리만 사용하기 때문에 코드의 공간 복잡도는 O(1)입니다.
Sympy.isprime() 메서드를 사용하여 소수를 확인하는 Python 프로그램
Sympy 모듈에서는 Sympy.isprime() 함수를 사용하여 주어진 숫자 n이 소수인지 여부를 테스트할 수 있습니다. n <2의 경우64대답은 확실합니다. n 값이 클수록 실제로 의사소수가 될 확률은 낮습니다.
파이썬3참고: 음수(예: -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)