[Algorithm] 백준 2581 소수

문제

문제 설명

 

맞았지만 오래 걸린 코드

m = int(input())
n = int(input())

result = 0
min = 0

for i in range(m, n+1):
    count = 0
    for j in range(2, i+1):
        if i % j == 0:
            count += 1
            if count == 2:
                break;
    if count == 1:
        result += i
        if min == 0:
            min = i

if min == 0:
    print(-1)
else:
    print(result, min)

 

왜 이렇게 오래 걸린 걸까?

그 이유는 9번째 줄 때문이다 

for j in range(2, i+1) 여기부분이 i + 1까지 전부 다 돌기 때문이다

 

그럼 왜 i + 1까지 돌 필요가 없는 걸까?

 

소수(素數, prime number)는 1보다 큰 자연수 중 1과 자기 자신만을 
약수로 가지는 수다 

 

만약 100이라는 수가 있다면 [ 100 ** (1/2) ](root) 해준만큼만 돌아도 된다.

그 이유는 11을 제곱한 수가 100을 넘기 때문에 돌지 않아도 된다는 말이다

 

말이 너무 어려운 것 같다..... 미래의 정훈이가 이해할 수 있겠지?

 

위의 방식을 사용하면 시간을 훨씬 단축할 수 있다

 

 

시간이 단축된 코드

m = int(input())
n = int(input())

result = 0
min = 0

for i in range(m, n+1):
    count = 0
    if i == 1:
        continue
    for j in range(2, round(i**(1/2))+1):
        if count == 2:
            break
        if i % j == 0:
            count += 2

    if count == 0:
        result += i
        if min == 0:
            min = i
    
if min == 0:
    print(-1)
else:
    print(result, min)

훨씬 줄었다 

 

고칠 점

1. If문을 너무 많이 사용한 것 같다 좀 더 깔끔하게 바꿀 필요가 있어 보인다.

 

잘한 점

1. 포기하지 않고 내 힘으로 풀었다