1. Problem 📃

https://programmers.co.kr/learn/courses/30/lessons/12921

정수 N을 입력받았을 때, 1~N 사이의 소수의 개수를 구하는 문제입니다.

2. Logic 👨‍🏫

에라토스테네스의 체

• 임의의 자연수 n에 대해 그 이하의 소수를 찾는 가장 간단하고 빠른 방법

1. N 이하의 모든 수를 소수라고 가정한다.
2. N의 제곱근까지 검사하며, 만약 소수를 발견한다면 그 수를 제외한 배수들을 소수가 아닌걸로 판명짓는다.
3. 그렇게 제곱근까지 검사하면 소수만 남게된다.

3. Code 💻

1. 내가 푼 코드

def solution(n):
    sieve = [True] * (n+1)

    m = int(n ** 0.5)
    for i in range(2, m + 1):            # n의 최대 약수가 sqrt(n) 이하
        if sieve[i] == True:             # i가 소수인 경우 
            for j in range(2*i, n+1, i): # i이후 i의 배수들을 False 판정
                sieve[j] = False

    return len([i for i in range(2, n+1) if sieve[i] == True])  # len()으로 개수 반환

2. 다른 분이 푼 코드

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)

4. Feedback 📚

"에라토스테네스의 체"라는 알고리즘을 처음 접하게 됐는데 되게 다양하게 접근한 사람들이 많이 보였다. 처음 이 문제를 접하고 풀게 됐을때 시간복잡도 앞에서 많이 헤맸는데 앞으로 어떻게 접근해야 할 지 방향을 잡아준 문제였다.

4.1 range(start, stop, step)

Parameter	Description
start	Optional. An integer number specifying at which position to start. Default is 0
stop	Required. An integer number specifying at which position to stop (not included).
step	Optional. An integer number specifying the incrementation.

4.2 Python 제곱과 루트 구하기

4.2.1 제곱

aⁿ 를 표현하는 방법 2가지
1. a ** n
2. math.pow(a, n)

4.2.2 루트

√x 를 표현하는 방법 2가지
1. x ** 0.5
2. math.sqrt(x)

4.3 리스트 생성하기

1. 리스트 생성하기(1)

temp = []
for i in range(1, 5):
    temp.append(i)

# 출력을 위한 코드입니다.
print(temp) # [1, 2, 3, 4]

2. 리스트 생성하기(2)

temp = [i for i in range(1,5)]

# 출력을 위한 코드입니다.
print(temp) # [1, 2, 3, 4]

2번과 같이 생성하는 방법을 오늘 공부하면서 처음 알았다. 간단해도 너무 간단한거 아닌가요ㅠㅠㅠ 파이썬 사랑해😭