이 튜토리얼은 숫자가 소수인지 아닌지를 확인하는 파이썬 프로그램을 작성하는 방법을 가르칠 것입니다.
코딩 테스트를 해본 적이 있다면 소수 테스트 또는 숫자가 소수인지 확인하는 수학 문제를 접했을 것입니다. 그리고 앞으로 몇 분 동안 이 질문에 대한 최적의 솔루션을 찾는 방법을 배우게 될 것입니다.
이 자습서에서는 다음을 수행합니다.
- 소수의 기초를 복습하고,
- 숫자가 소수인지 확인하는 Python 코드를 작성하고
- O(√n) 런타임 알고리즘을 얻기 위해 더 최적화하십시오.
이 모든 것에 대해 시작하겠습니다.
목차
프라임 번호란 무엇입니까?
소수의 기본 사항을 검토하는 것으로 시작하겠습니다.
정수론에서 자연수 n은 초기 정확히 두 가지 요소가 있는 경우: 1과 숫자 자체(n). 학교 수학에서 기억하십시오. i가 n을 균등하게 나누는 경우 숫자 i는 숫자 n의 인수라고 합니다. ✅
다음 표에는 몇 가지 숫자, 모든 요인 및 소수인지 나열되어 있습니다.
nFactorsIs Prime?11아니요21, 2예31, 3예41, 2, 4아니요71, 7예151, 3, 5, 15아니요
위의 표에서 다음을 쓸 수 있습니다.
- 2는 가장 작은 소수입니다.
- 1은 모든 숫자의 인수입니다.
- 모든 숫자 n은 그 자체의 인수입니다.
따라서 1과 n은 임의의 숫자 n에 대한 사소한 인수입니다. 그리고 소수는 이 두 가지 이외의 어떤 인수도 가질 수 없습니다.
이것은 2에서 n – 1로 갈 때 n을 나머지 없이 나누는 중요하지 않은 인수를 찾을 수 없어야 함을 의미합니다.
파이썬에서 숫자가 소수인지 확인하는 O(n) 알고리즘
이 섹션에서는 위의 접근 방식을 Python 함수로 공식화해 보겠습니다.
Python에서 range() 객체를 사용하여 2에서 n – 1까지의 모든 숫자를 반복할 수 있습니다.
Python에서 range(start, stop, step)은 범위 객체를 반환합니다. 그런 다음 범위 개체를 반복하여 시작부터 중지 -1까지 단계적으로 시퀀스를 얻을 수 있습니다.
2에서 n-1까지의 정수 집합이 필요하기 때문에 range(2, n)을 지정하고 for 루프와 함께 사용할 수 있습니다.
다음은 우리가 하고자 하는 일입니다.
- n을 나머지 없이 균등하게 나누는 숫자를 찾으면 해당 숫자가 소수가 아니라는 결론을 즉시 내릴 수 있습니다.
- n을 균등하게 나누는 숫자를 찾지 않고 2에서 n – 1까지 숫자의 전체 범위를 반복했다면 그 숫자는 소수입니다.
소수를 확인하는 파이썬 함수
위를 사용하여 다음과 같이 is_prime() 함수를 정의할 수 있습니다.
def is_prime(n):
for i in range(2,n):
if (n%i) == 0:
return False
return True
이제 위의 함수 정의를 구문 분석해 보겠습니다.
- 위의 함수 is_prime()은 양의 정수 n을 인수로 받습니다.
- (2, n-1)의 지정된 범위에서 인수를 찾으면 숫자가 소수가 아니므로 함수가 False를 반환합니다.
- 요인을 찾지 않고 전체 루프를 순회하면 True를 반환합니다.
다음으로 인수를 사용하여 함수를 호출하고 출력이 올바른지 확인하겠습니다.
is_prime(2) # True is_prime(8) # False is_prime(9) # False is_prime(11) # True
위의 출력에서 2와 11이 소수임을 알 수 있습니다(함수가 True를 반환함). 그리고 8과 9는 소수가 아닙니다(함수는 False를 반환합니다).
파이썬 함수 is_prime()을 최적화하는 방법
여기서 약간의 최적화를 수행할 수 있습니다. 아래 표의 요인 목록을 확인하십시오.
숫자팩터61, 2, 3, 6101, 2, 5, 10181, 2, 3, 6, 9, 18
음, n/2보다 큰 n의 유일한 인수는 n 자체임을 알 수 있습니다.
따라서 이것은 n – 1까지 반복할 필요가 없다는 것을 의미합니다. 대신 n/2까지만 루프를 실행할 수 있습니다.
n/2까지 중요하지 않은 요인을 찾지 못하면 n/2보다 큰 요인도 찾을 수 없습니다.
이제 is_prime() 함수를 수정하여 (2, n/2) 범위의 요소를 확인합니다.
def is_prime(n):
for i in range(2,int(n/2)):
if (n%i) == 0:
return False
return True
몇 가지 함수 호출을 통해 출력을 확인하겠습니다.
is_prime(9) # False is_prime(11) # True
최적화된 것처럼 보일 수 있지만 이 알고리즘은 런타임 복잡성 측면에서 이전 알고리즘보다 효율적이지 않습니다. 사실, 둘 다 O(n) 런타임 복잡성을 갖습니다. n 값에 비례하거나 n에서 선형입니다.
우리가 더 잘할 수 있습니까? 그래 우리는 할 수있어!
▶️ 소수 테스트의 시간 복잡도를 개선하는 방법을 결정하려면 다음 섹션으로 이동하십시오.
Python에서 소수를 확인하는 O(√n) 알고리즘
숫자의 요인이 쌍으로 발생합니다.
a가 숫자 n의 인수이면 axb = n 또는 간단히 ab = n인 인수 b도 존재합니다.
이를 예제를 통해 확인해보자.
아래 표는 쌍으로 발생하는 숫자 18의 인수를 보여줍니다. 원하는 경우 몇 가지 더 많은 번호에 대해 동일한 것을 확인할 수 있습니다.
또한 √18은 약 4.24입니다.
그리고 (a, b) 쌍으로 발생하는 요인에서 a가 4.24보다 작으면 b가 4.24보다 크다는 것을 알 수 있습니다(이 예에서는 (2, 18) 및 (3, 6)).
쌍으로 18의 인수
아래 그림은 숫자 선에 표시된 18의 인수를 보여줍니다.
숫자 n이 완전제곱수인 경우 a = b = √n을 인수 중 하나로 갖게 됩니다.
▶️ 아래 표에서 36의 인수를 보세요. 36은 완전제곱수이므로 a = b = 6도 요인 중 하나입니다. 다른 모든 요인 쌍(a, b)의 경우 a < 6 및 b > 6이 유지됩니다.
쌍으로 된 36의 인수
요약하면 다음과 같습니다.
- 모든 숫자 n은 다음과 같이 쓸 수 있습니다. n = axb
- n이 완전제곱수이면 a = b = √n입니다.
- 그리고 a < b이면 a < √n이고 b > √n입니다.
- 그렇지 않고 a > b이면 a > √n 및 b < √n입니다.
따라서 모든 정수를 n/2까지 반복하는 대신 √n까지 실행하도록 선택할 수 있습니다. 그리고 이것은 우리의 이전 접근 방식보다 훨씬 더 효율적입니다.
is_prime()을 O(√n) 알고리즘으로 수정하는 방법
파이썬에서 소수를 확인하기 위해 함수를 최적화해 봅시다.
import math
def is_prime(n):
for i in range(2,int(math.sqrt(n))+1):
if (n%i) == 0:
return False
return True
이제 위의 함수 정의를 구문 분석해 보겠습니다.
- 숫자의 제곱근을 계산하기 위해 Python의 내장 수학 모듈을 가져오고 math.sqrt() 함수를 사용합시다.
- n은 완전제곱수가 아닐 수 있으므로 정수로 변환해야 합니다. int(var)를 사용하여 var를 int로 변환합니다.
- 실제로 √n까지 확인하고 있는지 확인하기 위해 range() 함수가 기본적으로 범위의 끝점을 제외하므로 더하기 1을 추가합니다.
아래 코드 셀은 is_prime() 함수가 올바르게 작동하는지 확인합니다.
is_prime(8) # False is_prime(15) # False is_prime(23) # True
다음 섹션에서는 O(n) 및 O(√n)을 시각적으로 이해하기 위해 몇 가지 간단한 플롯을 만들어 보겠습니다.
O(n)과 O(√n)을 시각적으로 비교하기
▶️ 원하는 Jupyter 노트북 환경에서 다음 코드 스니펫을 실행하세요.
import numpy as np
import seaborn as sns
import pandas as pd
n = 20
x = np.arange(n)
y1 = np.sqrt(x)
y2 = x
df = pd.DataFrame({"O(√n)":y1,"O(n)":y2})
sns.set_theme()
sns.lineplot(data = df)
위의 스니펫은 값 범위에 대해 n 및 √n에 대한 곡선을 그리는 방법을 보여줍니다.
- NumPy range() 함수를 사용하여 숫자 배열을 만듭니다.
- 그런 다음 n과 √n의 값을 20까지(포함하지 않음) 수집합니다. 팬더 데이터 프레임.
- 다음으로 다음을 사용하여 플롯합니다. Seaborn의 선 플롯() 기능.
아래 플롯에서 √n이 n보다 훨씬 작음을 알 수 있습니다.
이제 범위를 최대 2000으로 늘리고 위와 동일한 단계를 반복합니다.
import numpy as np
import seaborn as sns
import pandas as pd
n = 2000
x = np.arange(n)
y1 = np.sqrt(x)
y2 = x
df = pd.DataFrame({"O(√n)":y1,"O(n)":y2})
sns.set_theme()
sns.lineplot(data = df)
위의 플롯에서 큰 숫자가 소수인지 테스트할 때 O(√n) 알고리즘이 훨씬 더 빠르다는 것을 추론할 수 있습니다.
다음은 간단한 예입니다. 2377은 소수입니다. 이것을 확인하십시오!😀
O(n) 접근 방식은 2000 단계를 취하지만 O(√n) 알고리즘은 단 49 단계로 답에 도달하는 데 도움이 될 수 있습니다.
결론
⏳ 이제 간략한 요약을 할 시간입니다.
- 숫자가 소수인지 확인하기 위해 순진한 접근 방식은 (2, n-1) 범위의 모든 숫자를 반복하는 것입니다. n을 나누는 인수를 찾지 못하면 n은 소수입니다.
- n/2보다 큰 n의 유일한 요소는 n 자체이므로 최대 n/2까지만 실행하도록 선택할 수 있습니다.
- 위의 두 접근 방식 모두 O(n)의 시간 복잡도를 갖습니다.
- 숫자의 인수는 쌍으로 발생하므로 √n까지만 실행할 수 있습니다. 이 알고리즘은 O(n)보다 훨씬 빠릅니다. 그리고 큰 수가 소수인지 아닌지 확인할 때 이득이 상당합니다.
파이썬에서 숫자가 소수인지 확인하는 방법을 이해하시기 바랍니다. 다음 단계로 문자열 연산에 대한 Python 프로그램 자습서를 확인할 수 있습니다. 여기에서 문자열이 회문, 아나그램 등인지 확인하는 방법을 배우게 됩니다.
다른 튜토리얼에서 모두 뵙겠습니다. 그때까지 해피코딩!👩🏽💻