https://school.programmers.co.kr/learn/courses/30/lessons/12921
1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.

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

제한 조건
n은 2이상 1000000이하의 자연수입니다.

시도

1

def solution(n):
    res = 0
    for i in range(2, n+1):
        if isPrime(i): res += 1
    return res

def isPrime(n):
    for i in range(2, n):
        if n%i==0: #1과 n외에 나눠떨어지면 소수아님
            return False
    return True

단순하게 품. 2부터 n까지의 수에 소수 검사 함수를 적용하여 소수면 res에서 1 더하도록 함.

결과

그럼 그렇지 ㅉㅉ O(n^2)이다

2(최종) - 에라토스테네스의 체

결국 난 구글링을 해버렸고.....!!!
내가 쓴 코드는 모든 소수를 구하는 데 부적합하다는 걸 알아냈고.....!!!

에라토스테네스의 체를 이용했다.

에라토스테네스의 체

범위에서 합성수를 지우는 방식으로 소수를 찾는 방법.
1. 1은 제거
2. 지워지지 않은 수 중 제일 작은 2를 소수로 채택하고, 나머지 2의 배수를 모두 지운다.
3. 지워지지 않은 수 중 제일 작은 3을 소수로 채택하고, 나머지 3의 배수를 모두 지운다.
4. 지워지지 않은 수 중 제일 작은 5를 소수로 채택하고, 나머지 5의 배수를 모두 지운다.
5. (반복)
참고: https://wikidocs.net/21638

def solution(n):
    a = [False, False] + [True]*(n-1)
    primes = []
    
    for i in range(2, n+1):
        if a[i]: #소수면
            primes.append(i) #소수 목록에 추가
            for j in range(2*i, n+1, i): #소수의 2배수부터 i만큼 뛰어넘으며 i의 배수 제거
                a[j] = False
    return len(primes)
                

결과

이것도 좀 오래걸리긴 하는데 어쨌든 통과

남의 코드

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)

이 코드도 에라토스테네스의 체이다.

그러나 이런 의견이......

참고

에라토스테네스의 체

https://wikidocs.net/21638