[단계별로 풀어보기] 기본 수학 2 - 소수 (2581)

2581번: 소수 (acmicpc.net)

2581번: 소수

이전 포스팅에서 사용했던 알고리즘들을 사용해 소수를 찾아보자.

 

방법 1. n까지 나누기

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

sosu = []

for i in range (m, n+1):
    isSo = True
    if i == 1:
        isSo = False
    for k in range (2, i):
        if (i%k) == 0:
            isSo = False
    if isSo == True:
        sosu.append(i)

if len(sosu) > 0:
    print(sum(sosu))
    print(min(sosu))
else:
    print(-1)

결과는?

for문이 너무 오랫동안 돌아서 시간이 초과됐다.

 

방법 2. n/2까지 나누기

시간을 줄이기 위해 for문의 실행시간을 절반으로 낮췄다.

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

sosu = []

for i in range (m, n+1):
    isSo = True
    if i == 1:
        isSo = False
    for k in range (2, int(i/2)+1):
        if (i%k) == 0:
            isSo = False
    if isSo == True:
        sosu.append(i)

if len(sosu) > 0:
    print(sum(sosu))
    print(min(sosu))
else:
    print(-1)

결과

2.436초 경과하여 성공하였다.

제한시간이 3초라서 아슬아슬했다.

 

방법 3. n의 제곱근까지 나누기

import math
m = int(input())
n = int(input())

sosu = []

for i in range (m, n+1):
    isSo = True
    if i == 1:
        isSo = False
    for k in range (2, int(math.sqrt(i))+1):
        if (i%k) == 0:
            isSo = False
    if isSo == True:
        sosu.append(i)

if len(sosu) > 0:
    print(sum(sosu))
    print(min(sosu))
else:
    print(-1)

결과

시간이 대폭 줄어 0.128초만에 통과되었다.

 

위 로직들에서 중요한 점은, i가 1일 때의 예외처리를 반드시 해주어야 제대로 동작한다는 점이다.