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

문제

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.

소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.(1은 소수가 아닙니다.)

제한 조건

• n은 2이상 1000000이하의 자연수입니다.

나의 풀이:

def solution(n):
    prime = [2]
    for i in range(3, n+1, 2):
        for j in range (3, i+1, 2):
            if i % j == 0:
                if j < i: break
                else: prime.append(i)
    return len(prime)

2를 제외한 나머지 소수는 짝수가 될 수 없다. 이 점을 기반으로 홀수만으로 계산하는 코드를 작성했는데 이중 for문, if문 때문에 효율성 테스트를 통과하지 못한다.

def solution(n)
		sieve = [True]*(n+1)

    m = int(n ** 0.5)
    for i in range(2, m+1):
        if sieve[i] == True:
            for j in range(i*i, n+1, i):
                sieve[j] = False

    x = [i for i in range(2, n+1) if sieve[i] == True]
    answer = len(x)
    return answer

일반적인 방법으로는 효율성 테스트를 통과하지 못해서 찾아본 결과 ‘에라토스테네스의 체’를 사용해야 한다고 한다. 위 코드가 에라토스테네스의 체를 사용해서 푼 코드인데, 아직 정확하게 이해를 못하겠다. 나중에 다시 돌아오자.