소수 찾기

문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/12921

---

코딩테스트 연습 - 소수 찾기

---

에라토스테네스의 체만 안다면 금방 풀 문제다! 제곱근을 구해준 후 그 범위 내에서 해당 수를 제외한 그 수의 배수들은 모두 True->False로 바꿔주고 result에 추가해주면 소수만 구할 수 있다!

이전에는 직접 소수를 하나하나 구했지만 에라토스테네스의 체를 사용하니 매우 간단하다,, 시간도 덜 걸린다!!

백준에서는 소수 문제 응용이 시간초과가 걸려 조금 다르게 풀었다,,

def solution(n):
    result=[]
    s=[True]*(n+1)
    m=int(n**0.5) #제곱근 구하기
    for i in range(2,m+1):
        if s[i]==True:
            for j in range(i+i,n+1,i): #배수는 모두 False로 바꿔주도록..!
                s[j]=False
    for i in range(2,n+1):
        if s[i]==True:
            result.append(i)
    return len(result)

 

 

---

 

 

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

->제가 이해하기 가장 쉬웠던 사이트입니다..!