[백준 1929] 소수 만들기

 

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

1929번: 소수 구하기

 

• 문제 설명

m과 n 두 수를 입력받고 두 수 사이의 소수를 모두 출력하면 되는 간단한 문제이다.

---

• 시간초과 제출 코드

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

for i in range(m,n+1):
    k = 2
    cnt = 0
    while k<i:
        if i%k == 0:
            cnt += 1
        k+=1
    if cnt == 0:
        print(i)

 

m부터 n까지 for문을 돌리면서 k와 cnt를 초기화해주었다. 이때 k는 1씩 증가하면서 나누어줄 수이고 cnt는 만약 나누어지면 소수가 아니니 이의 개수를 세어줄 카운터로 설정하였다. 개수가 0일 때만 출력하여 소수만 출력하였지만 시간초과가 나버렸다. 

 

• 제출 코드

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

for i in range(m,n+1):
    if i == 1:
        continue
    for j in range(2,int(i**0.5)+1):
        if i%j == 0:
            break
    else:
        print(i)

 

만약에 i가 12라고 쳤을 때 12는 2로 나눠 진다는 것이 확인이 되면 6으로도 나눠진다는 것이 확인이 되고 소수가 아니라는 것을 알 수 있다. 때문에, 나눌 때 for문을 i의 제곱근까지만 돌려줄 것이다. 그리고 나눠진다면 break를 통해 for문을 탈출하고 다음 수로 넘어가 줄 것이다. 

 

---

요즘 문제를 많이 풀지 않았더니 감도 잃고 풀었다 하면 시간 초과 나고 접근 자체를 하지 못하는 문제들이 많아졌다. 하루에 한문제씩이라도 꾸준히 풀고 풀지 못하더라도 계속 어떻게 풀 지 고민을 하면 생각하는 시간을 가져야 할 것 같다.