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

 

문제

 

1929번: 소수 구하기

 

 

 

 

 

정답 소스코드 (Python)

 

def if_decimal(num):
    if num==1:
        return
    for i in range(2,int(num**0.5)+1):
        if num%i==0:
            return
    count.append(num)


m,n=map(int,input().split())
count=[]                             # 몇 개 해당하는지
for i in range(m,n+1): if_decimal(i) # m과 n사이에 숫자 하나씩 확인
print(*count)

 

 

 

풀이  (Python)

 

 

 

어떤 수 n이 소수라는 것을 확인 하기 위해서는  해당 n보다 작은 자연수로 n을 나누었을 때 0이면 해당 수는 약수이다. 이때 자기자신을 제외한 약수가 생기지 않고, 1과 자기자신만을 약수로 가지는 것이 소수이므로, 반복문을 통해 자기자신을 제외한 약수가 있는 경우 소수가 아니고, 앞서 자기자신을 제외한 약수가 없는 경우 소수인 것으로 판별하여 해당 문제를 풀이하여야한다. 

 

 

위와 같이 풀이하는 경우 여러 수가 소수인지 아닌지 판별해야 하기 때문에, 많은 시간복잡도가 요구된다.

하지만 해당 범위내의 수들은 소수인지 아닌지 판별을 해야하는 것은 확실하므로 다른 곳에서 시간복잡도를 줄여야한다.

 

Point 1) √n까지 확인하기 

n=36
for i in range(1,int(n**(1/2))+1):
    if n%i==0:print(i,end =" ")

결과:

1 2 3 4 6

이와 같이 정상적으로 6전까지 출력되는 것을 볼 수 있다. 자연수 N의 절반까지 계산하는 방식의 시간 복잡도는 실제로 O(N)인 반면, 제곱근 까지 계산하는 방식은 시간 복잡도가 O( √N)으로 감소하는 것을 볼 수 있다.