Python_소수 찾기

---

<문제>

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요. 소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다. (1은 소수가 아닙니다.)

<제한 조건>

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

---

< 풀이 1단계>

def solution(n):
    answer = []
    for i in range(2,n+1):
        arr = []
        for j in range(1,i+1):
            if i%j == 0:
                arr.append(j)
        if len(arr) == 2:
            answer.append(i)
            del arr
    return len(answer)
# 테스트 케이스는 통과했으나 효율성 측면에서 실패

< 풀이 2단계>

def solution(n):
    li = [] 
    for n in range(2,n+1): 
        check = True 
        for i in range(2, int(n**0.5)+1): 
            if n%i == 0: 
                check = False 
        if check: 
            li.append(n)
            
    return len(li)
# 풀이 1단계보다 효율성은 높아졌지만, 통과 못함

< 풀이 3단계>

def solution(n):
    numbers = [True] * (n + 1)
    cnt = 0

    for i in range(2,int(n**0.5)+1):
        if numbers[i] == False:
            continue;

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

    for j in range(2,n+1):
        if numbers[j] == True:
            cnt+=1

    return cnt
# 통과

---

<다른 풀이>

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)

---

<풀이 3단계 코드 설명>

---