[이코테] 소수 구하기

해당 포스팅의 문제의 출처는 나동빈님의 이것이 취업을 위한 코딩 테스트 교재를 공부하면서 풀이할 때 본인의 사고 과정 흐름과 문제 풀이를 기록하기 위함 입니다. 

 

---

문제설명

하단의 백준 문제 링크 참조

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

1929번: 소수 구하기

사고과정

• 주어진 범위 내의 다수의 소수를 출력하는 문제다. 바로 에라토스테네스의 체 알고리즘을 활용
• m = 1로 주어질 수도 있으므로, 애초에 숫자 1은 소수가 아님을 처리

풀이

import math

n, m = map(int, input().split())
array = [True for _ in range(n+1)]

for i in range(2, int(math.sqrt(n))+1):
    if array[i] == True:
        j = 2
        while i * j <= n:
            array[i*j] = False
            j += 1

for i in range(m, n+1):
    print(i)