[python] 백준 2581번: 소수

이번 문제는 소수에 관련한 문제이다.

소수를 찾는 과정에서 반복문을 돌릴 때 범위를 전체로 하면 코드가 너무 많이 돌아야해서 시간 초과가 난다.

이를 해결하기 위해서는 일단 판단 해야하는 숫자들의 범위를 줄여야한다.

 

"어떤 수의 약수는 꼭 짝을 이루어서 나오게 된다."

 

이것이 바로 문제 해결의 솔루션이라고 생각한다.

짝을 이루어서 나오니, 판단 해야할 범위는 어떤 수의 제곱근 까지이다.

 

또한 구하는 과정에서 "에라토스테네스의 체"를 사용해야한다.

에라토스테네스의 체는 어떤 범위 내에서 아닌 숫자들을 다 제거해 나가는 방법이다.

체에 거르는 것과 같다고 하여 이름이 그렇게 붙여진 것 같다.

 

위 두 가지를 생각하면서 코드를 짜 보았다.

from math import sqrt
N=int(input())
M=int(input())
l=[i for i in range(N, M+1)]
for i in range(1,int(sqrt(M)+1)+1):
    if i==1:
        continue
    for k in l:
        if k==1:
            l.remove(k)
        if k%i==0 and k!=i:
            l.remove(k)
if len(l)==0:
    print(-1)
else:
    print(sum(l))
    print(min(l))

 

처음에 짠 코드이다.

물론 이렇게 해도 시간 초과 안나고 잘 돌아간다.

하지만 생각보다 시간이 꽤 오래걸리고, 이 소수 구하는 법을 활용해서 다른 문제를 해결하려고 했을 때(4948번같은)

무조건 시간 초과가 나서 시간을 단축 하는 방법에 대해서 고민해 보았다.

m=int(input())
n=int(input())
l=[1]*(n+1)
l[1]=0
for i in range(2, int(n**(0.5))+1):
    if l[i]:
        for j in range(i*i, n+1,i):
            l[j]=0

l=[i for i in range(m,n+1) if l[i] == 1]
if sum(l)==0:
    print(-1)
else:    
    print(sum(l))
    print(min(l))

그 결과물이다. 

처음 코드

나중 코드

시간은 거의 1/8로 단축되었다...!

실제 리스트를 만드는 것보다 인덱스로 처리하는 것이 훨씬 빨라진다는 것을 배웠고

시간을 단축하는 여러가지 방법에 대해서 공부를 할 필요성을 느꼈다..,,!