[백준] 1929번 : 소수 구하기 (Python / 파이썬)

• 문제

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

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

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

 

• 코드

# 입력부
start,end=map(int,input().split());

# 처리부
def isprime(k):
    if(k==1):
        return 0;
    for i in range(2,int(k**(1/2))+1,1):
        if(k%i==0):
            return 0;
    return 1;

# 출력부
for i in range(start,end+1):
    if(isprime(i)==1):
        print(i);

 

• 문제 풀이

에라토스테네스의 체로 문제를 푼다면, 시간 초과가 날 것이다.

(2부터 n까지 다 대입해서 나누기 때문에 숫자가 커질 수록 소요시간이 오래 걸린다.)

 

아까전 풀었던 코드를 그대로 가져와 start, end만 지정해서 풀었더니 시간 초과가 되었다.

# 입력부
start,end=map(int,input().split());

# 처리부
def isprime(k):
    if(k==1):
        return 0;
    for i in range(2,k,1):
        if(k%i==0):
            return 0;
    return 1;

# 출력부
for i in range(start,end+1):
    if(isprime(i)==1):
        print(i);

 

 

그렇다면 복잡도를 낮출 필요가 있다.

 

학기 중 교수님께서, 시간 복잡도를 낮추려면 범위를 int(루트배)+1만큼 하면 시간이 줄어들 것이라고 말씀하셨다.

그 때 간단하게 원리를 말씀해 주셨는데, 과정은 이해하지 못했고 결과만 기억하고 있던게 떠올랐다.

교수님께서 학년이 올라가면 알게 될 거라고 말씀하셨다. (교수님,, 학년이 올라가면 차차 이해 해 볼게요 ㅠㅠ...) 

 

그렇게 해서 풀었는데 통과했다.

 

---

• 여담

한 학기 동안 교수님한테 배운거 써 먹을 때마다 기분이 좋다.

뭔가 공부하는 느낌이 들기도 하고, 뭔가 영화 같은 곳에서 처음에 뿌린 퍼즐들이 영화 끝에서 하나씩 맞춰지는 느낌이랄까..

 

 

코드가 이상하거나, 이해가 되지 않는 부분은 언제든 댓글 남겨주세요! :)