(인프런) 파이썬 알고리즘 문제1-7 "소수(에라토스테네스 체)"

에라토스테네스의 체

[시간복잡도]

O(N²)

 

=> (한개의 변수를 가지고서 이중 for문을 돌렸기 때문에)

[공간복잡도]

O(N)

 

=> res 배열이 1차원 배열이고 ( heap memory 라는 메모리에 유동적으로 생성) / N, divisor_num 은 스택에 해당하며 두 요소(res배열:heap memory / N,divisor_num: 스택)가 메모리에 저장된다.

 

N, divisor_num 과 같은 변수들을 "고정공간" 이라고 부르고, res같은 1차원 배열은 "가변공간"이라고 부른다.

이 둘(고정공간, 가변공간)을 합친 것이 바로 "공간복잡도"이다.

 

Problem

소수(에라토스테네스 체) 자연수 N이 입력되면 1부터 N까지의 소수의 개수를 출력하는 프로그램을 작성하세요.

만약 20이 입력되면 1부터 20까지의 소수는 2, 3, 5, 7, 11, 13, 17, 19로 총 8개입니다.

제한시간은 1초입니다.

 

▣ 입력설명

 

첫 줄에 자연수의 개수 N(2<=N<=200,000)이 주어집니다.

 

▣ 출력설명

 

첫 줄에 소수의 개수를 출력합니다.

 

▣ 입력예제

 

20

 

▣ 출력예제

 

8

 

 

💯 Solution ①

: Only My Thinking (어려워서 선생님의 코드를 참고)

 

import sys
sys.stdin=open("input.txt","rt")
 
N=int(input())
# N개의 0으로 이루어진 리스트 생성
res=[0]*(N+1)
divisor_num=0
 
# 2부터 N까지 반복
for i in range(2,N+1):
    if res[i]==0:
        divisor_num+=1
        # i에서 N+1 까지 i씩 건너뛰어서
        for j in range(i,N+1,i):
            res[j]=1
 
print(divisor_num)

 

💯 Solution ②

: Tutor advice

 

(위와 똑같은 로직이다.)

import sys
sys.stdin=open("input.txt","rt")
n=int(input())
ch=[0]*(n+1)
cnt=0
 
for i in range(2, n+1):
    if ch[i]==0:
        cnt+=1
        # range(strat, end, step) : i에서 시작해서 n+1전까지 i씩 간격을 두고
        for j in range(i, n+1, i):
            ch[j]=1
print(cnt)

 

📚 참고

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

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

 

range

• 말그대로 범위로 for문의 대상 범위
• range(시작숫자, 종료숫자, step)의 syntax로 리스트의 슬라이싱과 유사
• 시작숫자와 step은 생략 가능

range example

>>> range(5)
range(0, 5)
>>> for i in range(5):
...     print(i)
... 
0
1
2
3
4

# 순서 있는 컬렉션으로 반환하고자 할 때
>>> range(5,10)
range(5, 10)
>>> list(range(5,10))
[5, 6, 7, 8, 9]
>>> tuple(range(5,10))
(5, 6, 7, 8, 9)

# step 활용
>>> list(range(10,20,2))
[10, 12, 14, 16, 18]
>>> list(range(10,20,3))
[10, 13, 16, 19]