[python] SWEA - 3131. 100만 이하의 모든 소수

🤔문제 해결

• D3 | 소수(에라토스테네스의 체)

💨 주어진 범위만큼의 길이를 가진 모든 원소가 1로 된 리스트를 만든다. ( 이 문제에서 범위는 10**6 )

💨 리스트의 0번째와 1번째는 미리 0으로 만들어둔다. ( 소수가 아니므로 )

💨 2부터 끝까지 반복문을 실행하면서

💨 해당 인덱스의 값이 0이 아니라면

💨 해당 인덱스를 제외한 배수의 인덱스의 값을 모두 0으로 바꿔준다. ( 소수가 아니므로 )

💨💨 EX) 2번째 값이 1이면 4, 6, 8 ... 은 모두 0으로 바꿔준다.

💨 원소의 값이 1인 녀석들은 모두 소수이다.

💻소스 코드

N = 10 ** 6 + 1
eratos = [1] * N
eratos[0], eratos[1] = 0, 0

for i in range(2, N):
    if eratos[i] == 1:
        for j in range(i * 2, N, i):
            eratos[j] = 0

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

📕문제 확인

출처: SW Expert Academy

SW Expert Academy