소수란, 1보다 큰 자연수 중에서 1과 자신을 제외한 자연수로는 나누어 떨어지지 않는 자연수.
import sys
# sys.stdin = open("input.text", "rt")
#소수 판별 함수(2 이상의 자연수에 대하여)
def is_prime_number(x):
#2부터 x-1까지의 모든 수를 확인하며
for i in range(2,x):
if x % i == 0:
return False #소수가 아님.
return True #소수임
print(is_prime_number(6))
print(is_prime_number(7))
2부터 n-1까지의 모든 자연수에 대하여 연산을 수행하기에 시간 복잡도 O(N)
성능 개선을 위해 약수의 성질 이용.
모든 약수가 가운데 약수를 기준으로 곱셈 연산에 대해 대칭을 이룬다.
따라서 특정한 자연수의 모든 약수를 찾을 때 가운데 약수(제곱근)까지만 확인하면 돼!!!
import sys
import math
# sys.stdin = open("input.text", "rt")
#소수 판별 함수(2이상의 자연수에 대하여)
def is_prime_number(x):
#2부터 x의 제곱근까지의 모든 수를 확인하며
for i in range(2, int(math.sqrt(x)) + 1): #제곱근에 1을 더해줌으로써 실질적으로 제곱근까지 확인!
#x가 해당 수로 나누어 떨어진다면
if x % i == 0:
return False
return True
#이렇게 제곱근까지만 확인한다면 뒤에 역시 동일하게 나온다는 걸 아니깐 시간복잡도에서 이득!
print(is_prime_number(4))
print(is_prime_number(7))
개선된 코드는 2부터 n의 제곱근까지의 모든 자연수에 대해서 연산을 수행하기 때문에
이제까지 하나의 수에 대해서 소수인지 아닌지를 판별하는 방법을 배웠다.
-> 특정한 수의 범위 안에 존재하는 모든 소수를 찾아보자.
이 알고리즘은 특정 범위 안에 존재하는 각각의 자연수들이 소수인지 아닌지를 한꺼번에 계산하고자 할 때 효과적으로 사용 가능.
이 과정을 수행하면 2부터 N까지 모든 자연수에 대하여 어떤 수가 남아 있는지를 확인해서 그 남아있는 수들이 모두 소수라고 판단할 수 있다.
import math
# sys.stdin = open("input.text", "rt")
N = 1000 #2부터 1000까지의 모든 수에 대하여 소수 판별
#처음엔 모든 수가 소수인 것으로 초기화(0과 1인 제외)
array = [True] * (N+1)
array[0] = False #0,1제외
array[1] = False #0,1제외
#에라토스테네스의 체 알고리즘 수행
#2부터 N의 제곱근가지의 모든 수를 확인하며
for i in range(2,int(math.sqrt(N)) + 1):
if array[i] == True: #i가 소수인 경우 (남은 수인 경우)
#i를 제외한 i의 모든 배수 지우기
j = 2
while i * j <= N:
array[i*j] = False #array[i]만을 남겨!
j += 1
#모든 소수 출력
for i in range(2,N+1):
if array[i] == True:
print(i, end = " ")
에라토스테네스의 체 알고리즘의 시간 복잡도는 사실상 선형 시간에 가까울 정도로 매우 빠르다.
😎 에라토스테네스의 체 알고리즘은 다수의 소수를 찾아야 하는 문제에서 효과적으로 사용될 수 있다 !!