프로그래머스 Lv1 소수찾기(python)

소수찾기

알고리즘 문제풀이를 안 했더니 감을 잃어서 다시 풀면서 실력을 쌓고 있다.
소수와 관련한 문제가 자주 나와서 좀 더 빠르게 소수여부를 확인할 수 없을까 하다가 에라토스테네스의 체를 알게 되었고, 잘 이용하고 있다.

우선 0과 1은 소수가 아니므로 제외하고 2 ~ n이라는 숫자가 있을 때, n까지의 숫자 중 소수가 무엇인지 확인할 때 사용하면 된다.

알다시피 소수는 1과 자기 자신으로만 나눴을 때 나머지가 0인 수를 말한다.

보통이라면 2~n까지의 숫자 i를 모두 돌면서 확인할 텐데 i를 2~(i-1)까지 또는 2~(((i-1)//2)) 까지 돌리면서 i % 해당값 == 0 이면 소수 아님의 방식으로 할 수 있다. 그러나 이 경우 모든 수를 다 확인하게 되므로 시간적으로 비효율적이다.

따라서 처음부터 확인을 하되, 소수의 배수들은 모두 약수가 있으므로, 소수가 될 수 없음을 인지하고 제외시킬 것들을 제외하는 방식으로 1~n까지의 숫자 중 소수를 찾는 방식이다.

이를 숫자 100까지의 소수를 구하시오라는 예제가 있을 때, python 코드로 보이면 아래와 같다.

n = 100
#  boolean으로 n+1개의 리스트를 생성
# 이 때 [False, False]의 이유는 0과 1은 소수가 아니기 때문
a = [False, False] + [True] * (n-1)
# 생성될 소수는 sosu리스트에 입력
sosu = []
# 2부터 n까지 소수여부 확인시작
for i in range(2, n+1):
	# 우선 처음 만나는 True인 i는 소수일테니까 소수 리스트에 입력
    if a[i]:
    	sosu.append(i)
    # 소수의 배수는 소수가 될 수 없음에 아래의 코드 작성
	# i의 2의 배수 부터 n까지, i의 모든 배수를 False로 바꾸기
    for j in range(2*i, n+1, i):
    	a[j] = False
    print(sosu)

풀이

위 에라토스테네스를 이용해서 프로그래머스의 소수 찾기 문제는 다음처럼 풀었다.

# 에라토스테네스의 체 사용
def solution(n):
    a = [False, False] + [True] * (n-1)
    sosu = []
    for i in range(2, n+1):
        # 우선 처음 만나는 True인 i는 소수일테니까 소수 리스트에 입력
        if a[i]:
            sosu.append(i)
        # i의 2의 배수 부터 n까지, i의 모든 배수를 False로 바꾸기
        for j in range(2*i, n+1, i):
            a[j] = False
    return len(sosu)

다른 사람 풀이

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)