[Python][SWEA] 3131. 100만 이하의 모든 소수 D3

SW Expert Academy

---

 

🗒️ 파이썬 코드 풀이

num = 1000000
lst = [i for i in range(num)]

for i in range(2,num):
    for j in range(i,num,i) :
        if lst[j] == i:
            continue
        lst[j] = 0

for i in range(num) :
    if lst[i] == 1:
        continue
    if lst[i] == 0:
        continue
    print(i,end=" ")

 

1. 0~1000000까지의 수를 만들어준다. ( 0부터 하는 이유는 인덱스의 값과 실제 값을 통일시키기 위해)

 

2. 에라토스테네스의 체 알고리즘 이용  (순차적으로 n의 배수들 제거)

(1배(기존 값)는 0으로 만들어주지 않음)

 

3. 리스트의 소수들을 0으로 초기화

 

4. 리스트의 값이 1 또는 0인  경우 출력하지 않음

 

에라토스테네스의 체를 사용한 대표적인 알고리즘으로 전체 리스트에서 n의 배수들은 하나식 제거해준다. 

 

🧐 문제 코멘트

에라토스테네스의 체 개념을 모르고 문제를 보았다. 처음에는 DP인가 했는데, DP방식으로는 잘 풀리지 않았다.

크기가 100만이라 2중 반복문도 조심스러운 시간 복잡도이다.

이 알고리즘을 아닌지 모르는지의 차이는 큰 것 같다.  

---

📚 문제

1 이상 100만(106) 이하의 모든 소수를 구하는 프로그램을 작성하시오.

참고로, 10 이하의 소수는 2, 3, 5, 7 이다.

[입력]

이 문제의 입력은 없다.

[출력]

1 이상 100만 이하의 소수를 공백을 사이에 두고 한 줄에 모두 출력한다.