백준 문제 중 1929번, 수학, ‘소수 구하기’

백준 문제 중 1929번

https://www.acmicpc.net/problem/1929

문제

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

입력

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

출력

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

---

풀이

Try1

m,n = map(int, input().split())


for i in range(m,n+1):

    # 1은 제외
    if i==1:
        continue

    # i를 2 ~ i-1로 나누우 나누어 떨어지지 않을때 소수 판별
    for j in range(2,i):
        if i%j==0:
            break
    else:
        print(i)

1 10
2
3
5
7

이렇게 코드를 구성 했으나 시간초과로 실패했고 알고리즘 개선이 필요했다.

Try2

m,n = map(int, input().split())


for i in range(m,n+1):
    if i==1:
        continue

    j=2

   # 약수의 성질 이용
    while j**2<=i:
        if i%j==0:
            break   
        j+=1
    else:
        print(i)

10 20
11
13
17
19

예를 들어 100의 약수인 [1,2,4,5,10,20,25,100]에서 각각 (1,100) (2,50) (4,25) (5,20) (10,10) 으로 서로 곱해서 100이 되는 쌍을 가지고 있다. 이때 각 쌍중 작은 수 만으로 나누어봐도 100이 소수인지 아닌지 판뵬이 가능하고 이때 기준은 100의 제곱근 10 이하 인 수 까지만 나누어 봐도 판단 할 수 있음을 알 수 있다.

약수들의 성질을 이용해서 검색하는 j의 범위를 i의 제곱근 보다 작거나 같을때 까지로 개선 했으나 시간초과로 실패했다.

Try3

def is_prime(x:int)->bool:
    if i==1:
        return False

    j=2
    while j**2<=i:
        if i%j==0:
            return False  
        j+=1
    else:
        return True

m,n = map(int, input().split())

for i in range(m,n+1):
    if is_prime(i):
        print(i)

1 10
2
3
5
7

소수를 판단하는 함수를 만들고 이를 이용해 직접 소수를 구하는 기존의 방법보다 빠르게 개선했다.

배운점

알고리즘을 개선 시켜 나가는 과정을 배울 수 있었다.