[알고리즘] 소수 판별하기
1. 소수
1보다 큰 자연수 중에서 1과 자기자신을 제외한 자연수로 나누어떨어지지 않는 수를 의미한다.
1-1. 선형탐색 - 약수의 성질을 이용하여 범위 최소화
모든 수 N에 대하여 소수 여부를 확인하고자 할 떄는, 선형탐색(접근)보다는 경우의 수를 최대한 낮추어 알고리즘을 적용하는 것이 중요하다(선형탐색일 경우 시간복잡도가 그만큼 비례하여 증가).
- 이때 약수의 성질을 이용하는데, 모든 약수가 가운데 해당 수의 제곱근을 기준으로 곱셈에 대한 대칭이 이루어진다는 점을 이용한다.
- 즉, 제곱근 전까지 해당 수가 나누어 떨어지는 몫이 존재하는 여부를 파악한다면 범위를 최소화할 수 있는 상태에서 소수여부에 대해 판별이 가능하다.
- 시간복잡도는 O(N^1/2)이다.
#소수 판별하기
import math
def isPrimeNumber(x):
for i in range(2, int(math.sqrt(x))+1):
if x % i == 0:
return False
else:
return True
print(isPrimeNumber(5))
1-2. 에라토스테네스의 체 - 특정 수 범위 내에서 존재하는 모든 소수 탐색
보통은 한가지 수에 대한 소수여부보다는, 여러 수에 대해 소수여부를 판단할 수 있는지에 대해 구현할 수 있는지가 더 중요하다.
- 즉 여러개의 수에 대해 반복적으로 소수여부를 판단해야 하는 경우
- 특정 범위에 속하는 모든 소수를 구해야 하는 경우
이런 상황일 경우엔 에라토스테네스의 체 알고리즘을 활용하는 것이 더 유리하다.
N보다 작거나 같은 자연수에서 존재하는 모든 소수를 찾고자 할 때, 아래 과정을 반복한다.
- 2부터 N까지 모든 수를 나열한다.
- 최초 시작 수 i를 정한다(단 i는 일전 과정에서 처리되지 않은 수).
- i의 배수를 모두 제거한다.
- 위 과정을 반복한다.
이때 유의해야 할 점은, N이하의 수 중 소수인 수를 "남아있게 하는 것"이 중요하다는 것이다. 즉, 소수가 아닌 수들은 최초 소수에 2,3,4,..를 곱해가면서 제거되며 이 "곱해지는 소수"들은 제곱근보다 큰 수를 찾을 필요없이 작은 범위 내에서 찾는다.
다만 제거하는 수는 모든 범위에서 진행, "곱해지는 소수"만 제곱근 범위 내에서 진행
import math
# 1000까지의 소수 판별
n = 1000
array = [True for i in range(n+1)]
for i in range(2, int(math.sqrt(n))+1):
#어떤 수의 배수들을 제거할지 판단하는 기준은
#최초의 소수를 제외하고, 그 소수의 모든 배수를 제거한다.
if array[i] == True:
j = 2
while i * j < n:
#소수가 아닌 수들은
#n의 제곱근 안에 속하는 약수들에 대하여
#그 배수들이 제거되므로
#곱하는 수 자체는(i)는 제곱근 내부의 수
#단 제거할 때는 모든 범위에 대해서 제거
array[i*j] = False
j = j + 1
#모든 소수 출력
for i in range(2, n+1):
if array[i]:
print(i, end=' ')
Author And Source
이 문제에 관하여([알고리즘] 소수 판별하기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@gyrbs22/알고리즘-소수-판별하기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)