[프로그래머스, 파이썬] 소수 찾기

풀이

• 처음에는 특정 수의 절반까지만 조회를 하는 코드를 적용했는데
• 해당 코드는 시간초과와 효율성 문제로 해결되지 못하였다.
• 그래서 찾아보니 특정 수의 제곱근까지만 약수를 확인하면 된다고 하여
• 첫 번째 풀이는 round(i**(1/2))까지 탐색하도록 하니 해결할 수 있었다.
• 그리고 두 번째 풀이는 에라토스테네스의 체를 사용한 방법으로
• 대량의 소수들을 구할 때 사용하는 알고리즘이라고 해서 사용해봤는데
• 해당 알고리즘은 특정 수의 배수를 범위까지 조사하며 지우는 것으로
• 2번째 for문에서 i에 해당하는 배수부터 시작해서, n까지 조사하되, i만큼 계속 j가 커지도록 하여 조사하기.
• 효율성 시간을 확인해보니 확실히 차이가 있는 것을 확인할 수 있음.

 

기본 풀이

def solution(n):

    result = [2]

    for i in range(3,n+1):

        state = True

        rng = round(i**(1/2))

        for j in range(2,rng+1):

            if not i%j:

                state = False

                break

        if state: result.append(i)

    return len(result)

에라토스테네스의 체 풀이

def solution(n):

    li = [1]*(n+1)

    for i in range(2,n+1):

        if li[i] != 0:

            for j in range(2*i,n+1,i): li[j] = 0

    return sum(li[2:])