[프로그래머스] 소수 찾기 Lv.1

소수 찾기가 잘 풀리지 않아 구글링을 한 결과 따로 함수를 작성한 후 이용하여 풀어도 되지만
에라토스테네스의 체를 이용하는 것이 훨씬 시간복잡도 면에서 안정성도 있고 종합적으로 효율성이 매우 좋아 소수를 찾을 때 자주 이용하는 알고리즘이라 한다.

이번에는 에라토스테네스의 체를 따로 공부해보고자 한다.

<우선 내가 억지로 작성한 코드>

def isPrime(num):
    for i in range(2, int(num ** 0.5)+1):
        if num % i == 0:
            return False

    return True



def solution(n):
    
    result = 0
    
    # 소수는 1과 자기자신 제외하면 자연수 중 어떤 숫자로도 떨어지지 않는 숫자
    # 1은 포함 X, 에리토스테네스의 체
    # --------------------------------------------      
    # 2부터 N까지의 모든 자연수를 나열한다.
    # 남은 수 중에서 아직 처리하지 않은 가장 작은 수 i를 찾는다.
    # 남은 수 중에서 i의 배수를 모두 제거한다.(i는 제거하지 않는다.)
    # 더 이상 반복할 수 없을 때까지 2번과 3번의 과정을 반복한다.
    
    
    # 2부터 n까지(제곱근) 모든 수 나열
    for i in range(2, n + 1):
        if isPrime(i) != 0:
            result += 1

    return result

소수를 구하는 함수를 따로 작성하여 풀었으나 효율성 면에서 매우 안좋은 모습을 보였다.

<에라토스테네스의 체>

1. 2부터 N까지의 모든 자연수를 나열한다.
2. 남은 수 중에서 아직 처리하지 않은 가장 작은 수 i를 찾는다.
3. 남은 수 중에서 i의 배수를 모두 제거한다.(i는 제거하지 않는다.)
4. 더 이상 반복할 수 없을 때까지 2번과 3번의 과정을 반복한다.

<에라토스테네스의 체를 이용해 작성한 코드>

import math

n = 1000	# 2부터 1000까지 모든 수에 대하여 소수를 찾을 것이다.
array = [True for i in range(n + 1) # 0,1을 제외한 모든 숫자가 소수(True)인 것으로 설정하고 시작한다.

# 에라토스테네스의 체 알고리즘
for i in range(2, int(math.sqrt(n)) + 1): # 2부터 n의 제곱근까지의 모든 수를 확인
	if array[i] == True:	# i가 소수인 경우
    	# i를 제외한 i의 모든 배수를 지우기
        j = 2
        while i * j <= n:
        	array[i * j] = False
            j += 1
            
#모든 소수 출력
for i range(2, n + 1):
	if array[i]:
    	print(i, end = ' ')

이 알고리즘은 생각보다 속도가 매우 빠르다.

따라서 다수의 소수를 찾는 문제를 굉장히 빠르게 해결할 수 있지만,

N의 크기만큼 리스트를 만들어서 할당해야하기 때문에 굉장히 많은 메모리를 필요로하는 단점이 있다.

대략 십억이 넘어가는 크기의 숫자가 되면 해당 알고리즘 말고 다른 알고리즘을 생각해봐야한다.

1. 시간 복잡도는 사실상 선형 시간에 가까울 정도로 매우 빠르며, O(NloglogN) 이다.

2. 다수의 소수를 찾아야 하는 문제에서 효과적으로 사용될 수 있다.

하지만, 각 자연수에 대한 소수 여부를 저장해야 하므로 메모리가 많이 필요하다.

<프로그래머스 소수 찾기 Lv.1> - 에라토스테네스의 체 알고리즘 이용

def solution(n):
    num=set(range(2,n+1))

    for i in range(2,n+1):
        if i in num:
            num-=set(range(2*i,n+1,i))
    return len(num)

• 출처 : https://unie2.tistory.com/311,
  https://unie2.tistory.com/311