SWEA(Python) 풀이/D3

SWEA[D3] (Python) 3131번 100만 이하의 모든 소수 풀이

개발윗미 2022. 5. 25. 16:56

Python으로 구현한 3131번 100만 이하의 모든 소수 문제 풀이입니다.

 

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=3&contestProbId=AV_6mRsasV8DFAWS&categoryId=AV_6mRsasV8DFAWS&categoryType=CODE&problemTitle=&orderBy=FIRST_REG_DATETIME&selectCodeLang=PYTHON&select-1=3&pageSize=10&pageIndex=8 

 

SW Expert Academy

SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

swexpertacademy.com


n = 10 ** 6 + 1
data = [1] * n
data[0], data[1] = 0, 0

# 배수 처리
for i in range(2, n) :
    if data[i] == 1 :
        for j in range(i * 2, n, i) :
            data[j] = 0

for i in range(n) :
    if data[i] == 1 :
        print(i, end=' ')

 

1. 문제에서 주어진 범위만큼의 길이를 가진 data 리스트의 요소들을 모두 1로 초기화한다.

 

2. data[0], data[1] 의 값은 소수가 아니므로 0으로 갱신한다.

 

3. 2부터 n까지를 범위로 하여 data[i]가 1일 경우(소수일 경우) 해당 수의 배수를 모두 0으로 갱신한다.

 

4. data 리스트에 존재하는 값이 1인 경우에만 해당 수를 출력한다.