[인프런](python) 소수(에라토스테네스의 체)

---

🧩 소수(prime number)

• 1보다 큰 자연수 중 1과 자기 자신만을 약수로 갖는 수
• n이하의 소수는 √n 을 넘지 않는다

---

🧩 에라토스테네스의 체

---

🏁 내 풀이

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

    return len([i for i in range(2,n) if numbers[i] == True])

---

📌

• numbers[ ] : n이하의 모든 수
• m : 계산할 리스트 길이
• i=2, 2의 배수 False로 만들고
  또 True만 모아 i=3의 배수 False

---