소수 찾기 1단계, Python3 [프로그래머스]

 

문제 설명

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

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

제한 조건

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

입출력 예

nresult

10	4
5	3

 

 

---

음.. 이것은 에라토스테네스의 체처럼. 미리 만들지 않으면 시간 초과가 나는 문제이다.

즉, 하나하나 소수로 따지면 끝이 없다는 이야기다.

 

모두다 아래와 같이 에라토스테네스의 체를 만들어 거른다.

for문이 많이 돌아갈 것처럼 보이지만 그렇게 많이 돌아가지는 않는다.

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

    m = int(n ** 0.5)
    for i in range(2, m + 1):            # n의 최대 약수가 sqrt(n) 이하
        if sieve[i] == True:             # i가 소수인 경우 
            for j in range(2*i, n+1, i): # i이후 i의 배수들을 False 판정
                sieve[j] = False

    return len([i for i in range(2, n+1) if sieve[i] == True])  # len()으로 개수 반환

 

1. 체의 크기 설정

2. 최대 약수가 sqrt(n) 이하인 것은 수학적으로 생각

3. 소수인 경우 그 이후의 배수 처리

 

워낙 유명해서 코테에 나올 것 같진 않지만 알아는 둬야 한다. 소수 문제는 까다롭기 때문에