[프로그래머스_Lv1] 소수 찾기

소수 찾기

문제 링크

나의 풀이

# 첫번째 작성 코드
def solution(n):
    answer = ""
    answer = list(str(answer))
    for i in range(1, n+1):
        a = 0
        for j in range(1, i+1):
            if i % j == 0:
                a += j
        if a == i + 1:
            answer.append(i)
    return len(answer)

• 이중반복문을 사용하여 자연수 n(i)을 n보다 작은 자연수(j)들로 나눠주었을때 나머지가 0인경우 변수 a에 할당하고 a가 i+1과 같은 경우 answer 리스트 변수에 append해주는 코드이다. 로직자체가 틀리진 않았으나 굉장히 비효율적이라서 효율성 테스트에서 실패하였다.

# 두번째 작성 코드
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) 

• 2부터 n까지의 집합을 설정한 후, i를 제외한 i 이후의 i의 배수들을 제거해 가는 작업을 반복문을 통해 실행한다. 남아 있는 자연수가 소수이다. 이는 "에라토스테네스의 체" 개념을 구현한 코드이다. 이 개념을 완전히 이해하면 코드 작성이 아주 어렵지는 않다. 일종의 노가다 방식이긴 하지만 일정 범위내에서 소수를 찾아야 하는경우 에라토스테네스의 체보다 효율적인 방법은 아직 없는 것으로 알고있다.