[백준/Python] - 1929번 소수 구하기

https://www.acmicpc.net/problem/1929

📜제출코드 

import sys

import math

input = sys.stdin.readline

M, N = map(int, input().split())

#1과 0은 무조건 True이기 때문

prime = [True for _ in range(N+1)]

prime[0], prime[1] = False, False

for i in range(2, int(math.sqrt(N))+1):

    if prime[i] == True:

        j = 2

        while j * i <= N:

            prime[i*j] = False

            j += 1

for i in range(M, N+1):

    if prime[i] == True:

        print(i)

 

📜풀이

에라토스테네스의 체를 이용해서 소수를 찾으면 된다.

 

📜에로트스테네스의 체란?

체를 치듯이 수를 걸러낸다고 하여 에라토스테네스의 체라는이름이 붙었는데 

에라토스테네스의 체 - 파이썬

필자도 이 블로그 보고 이해를 했듯이 설명이 정말 잘되어있다.

 

다시 문제로 와서 M이상 N이하의 소수를 모두 출력해야한다.

 

1. 에라토스테네스의 체 초기화해주기

prime = [True for _ in range(N+1)]

prime[0], prime[1] = False, False

N범위 까지니까 N+1까지 범위를 적용해준다.

0 과 1은 소수가 아니니까 False로 초기화 해준다.

 

2. 소수 판별하기

for i in range(2, int(math.sqrt(N))+1):

    if prime[i] == True:

        j = 2

        while j * i <= N:

            prime[i*j] = False

            j += 1

 

📜N의 제곱근까지 해주는 이유는

16을 예시로 들어보겠다.

 

16의 약수로는 

1 2 4 8 16이다.

16의 약수들은 4를 기준으로 대칭적인 쌍을 이룬다.

어짜피 8과 4 16은 2에 의해서 False로 변할것이다.

 

i가 2일때 

2가 True이면

N까지 2의 배수들을 모두 지운다.

 

i가 3일때

3이 True이면

N까지 3의 배수들을 모두 지운다.

 

이런식으로 sqrt(N)까지 돌아주면 배수들이 모두 없어진다.