Level 1. 소수 찾기

31. 소수 찾기

코딩테스트 연습 > 연습문제 > 소수 찾기
https://programmers.co.kr/learn/courses/30/lessons/12921

---

문제 설명

Input value =

• n = 2 이상 100,000,000 이하의 자연수

Output value =

• range(2,n)에서 소수의 개수

---

제한 조건

ㆍ n은 2이상 100,000,000 이하의 자연수이다.

---

문제 구상

# 00
n = 10

# 01
num = set(range(2,n+1))

# 02
for i in range(2,int(n**0.5)+1):
    if i in num:
        num -= set(range(i*i,n+1,i))

# 03
len(num)

---

문제 풀이

def solution(n):
    num=set(range(2,n+1))
    for i in range(2,int(n**0.5)+1):
        if i in num:
            num -= set(range(i*i,n+1,i))
    return len(num)

# Code test
n = 10
solution(n)

---

마치며

1. set을 이용하여 에라토스테네스의 체에 걸러지는 원소들을 - 함으로써 연산속도 증가

2. 소수싫다..