[BOJ] 1929. 소수 구하기(python)

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오. 문제 보러 가기

 

입력
첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

출력
한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

---

테스트케이스

입력:

3 16

 

출력: 

3

5

7

11

13

---

코드

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

for i in range(M, N + 1):
    if i < 2:
        continue
    flag = True
    for k in range(2, int(i**0.5) + 1):
        
        if i % k == 0:
            flag = False
            break
    if flag:
        print(i)

---

회고

에라토스테네스의 체 알고리즘을 써야 하는지 모르고 냅다 들이박았는데..

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

for i in range(M, N + 1):
    flag = True
    for k in range(2, i):
        if i % k == 0:
            flag = False
            break
    if flag:
        print(i)

복잡도가 O(N^2)이 되면서 시간 초과가 떴다. 심지어 1 제외 조건도 없음,,

앞으로는 틀리지 말아야지 ㅎㅎ

💡 int()함수는 소숫점 이하를 버린다.