소수 찾기

소수 찾기

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

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

제한 조건

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

입출력 예

 

n	result
10	4
5	3

입출력 예 설명

 

입출력 예 #1
1부터 10 사이의 소수는 [2,3,5,7] 4개가 존재하므로 4를 반환

 

입출력 예 #2
1부터 5 사이의 소수는 [2,3,5] 3개가 존재하므로 3를 반환

---

나의 풀이

def solution(n):
    sum = 0
    s = 0
    for i in range(2,n+1):
        for j in range(2,i):
            if i % j == 0:
                s += 1
        if s == 0:
            sum += 1
        s = 0
    return sum

흐름대로 풀었다. for문을 두개 사용하여 소수를 찾았고, if문을 이용하여 걸러냈다.

 

다른사람의 풀이

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)

소수판별 알고리즘인 에라토스테네스의 체이다. 소수는 '양의 약수를 두개만 가지는 자연수'를 의미하므로, 소스를 대량으로 빠르고 정확하게 구하는 방법이라고 알려져 있다. for문을 하나만 쓰기 때문에 시간복잡도를 크게 줄일수 있다.

방법은 간단하다. 자기 자신은 가만히 두고, 2부터 시작해서 구하고자 하는 범위내에서 2의 배수를 모두 제거, 3의 배수를 모두 제거, ....

 

참고자료 : blog.naver.com/ndb796/221233595886

22. 에라토스테네스의 체