1929. 소수구하기

문제
M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.
출력
한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

예제 입력

3 16

예제 출력

3
5
7
11
13

---

import sys

def is_prime(n):
    if n == 1:
        return (0)
    i = 2
    while i * i <= n:
        if n % i == 0:
            return (0)
        i += 1
    return (1)

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

if M == 2:
    sys.stdout.write(str(M) + '\n');
if M == 1 and N >= 2:
    sys.stdout.write(str(2) + '\n')
    M += 2
if M % 2 == 0:
    M += 1
i = M
while i <= N:
    if is_prime(i):
        sys.stdout.write(str(i) + '\n')
    i += 2

---

is_prime함수는 인자로 받은 수가 소수인지 판별하는 함수인데, n이 1이면 바로 종료되고, 2와 3일때는 while문에 한번도 걸리지 않고 바로 참을 리턴한다. while문의 조건에서 i가 2부터 n-1까지 모든 수를 나눠가며 약수인지 아닌지 검사를 했다면 시간 초과가 떴을 것이다. n의 제곱근 까지만 i에 넣어가며 검사한 이유는 n이 소수가 아니라면 n은 1과 자기 자신이 아닌 두 수(a, b)의 곱(n = a*b)으로 이루어져있을 것이고, n의 제곱근(a=b인 경우)을 넘어 가면 앞에서 확인한 약수를 중복으로 확인하는 것이 된다.(n = a*b = b*a)

얼마 전에 씨언어로 소수 구하기 함수를 만들었던 기억으로 금방 풀 수 있었다.
M부터 N까지의 수를 소수 판별 함수에 넣는 것 보다는 판별할 숫자의 범위에 2가 들어가면 2만 출력해준 뒤 홀수로만 체크하기 위해 i의 초기값을 홀수로 셋팅시킨 후 2씩 증가시켜주었고, 홀수인지 짝수인지 판별하는 조건문을 while문 안에 넣고싶지 않아서 밖으로 뺐더니 조건식이 중복 되는 것이 많아져 가독성은 좀 떨어지는 것 같다.
(가독성이 좋은 코드와 성능이 좋은 코드 중 하나를 선택해야할 때마다 고민이 많이 된다. 이 문제같은 경우는 간단해서 조건문들을 while문 안에 넣었어도 성능에 있어 큰 차이는 없었겠지만 연산이 조금이라도 복잡해진다면 시간에 있어 성능 차이가 발생할 것 같아서 일단 들여쓰기가 최소화 되는 코드를 우선적으로 선택하는 편이다.)
근데 다 짜고 보니까 너무 씨언어처럼 코딩했다 ㅋ 파이썬 내장함수를 자유자재로 다루는 그날까지,,,,