[알고리즘] 백준 1929 (파이썬 풀이)

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

1929번: 소수 구하기

문제

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

입력

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

출력

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

 

풀이코드

1차실패코드

m, n = map(int, input().split())
li= []

for i in range(m, n+1):
    cnt = True
    for j in range(2, i):
        if(i%j == 0):
           cnt = False
           break
    if(cnt==True):
        li.append(i)

for i in li:
    print(i)

실패이유 : 일단 계속 백준에서 시간초과가 떴기 때문에 다른 오류를 발견하지 못했음.

그래서 시간초과를 해결하기 위해 아래의 코드 작성함

 

2차 실패 코드

import sys
import math

m, n = map(int, sys.stdin.readline().split())
li= []

for i in range(m, n+1):
    cnt = True
    for j in range(2, int(math.sqrt(i))+1):
        if(i%j == 0):
           cnt = False
           break
    if(cnt==True):
        li.append(i)
for i in li:
    print(i)

실패이유 : 입력 시간을 줄이기 위해 readline()을 사용하고 소수인지 확인하기 위해 값의 제곱근까지만

확인하는 방식을 사용했다. 시간초과는 뜨지 않았지만 실패라는 결과가 나왔다. 반례를 찾지 못해 애를 먹었다.

 

완성코드

import sys
import math

m, n = map(int, sys.stdin.readline().split())
li= []

for i in range(m, n+1):
    cnt = True
    for j in range(2, int(math.sqrt(i))+1):
        if(i%j == 0):
           cnt = False
           break
    if(cnt==True):
        li.append(i)
if(1 in li):
    li.pop(0)
for i in li:
    print(i)

이 코드로 문제를 맞추게 되었는데, 반례를 찾았다. 문제에서 m의 범위가 1까지 포함이었던 것을 보지 못했다.

당연히 2부터라고 생각했는데 1도 범위에 들어가서 저 조건대로 코드를 실행하면 리스트에 1까지 포함이 된다.

그래서 마지막에 조건문으로 리스트에 1이 포함되어 있다면 0번째 위치에 있는(1은 항상 맨앞에 위치) 값을 제거하게

작성하였더니 성공하였다.

 

전체코드풀이

시간복잡도를 줄이기위해 sys, math 라이브러리를 사용한다.

map(int, sys.stdin.readline().split())을 이용하여 한 줄에 m과 n을 입력받는다.

소수를 넣어줄 li라는 리스트를 한 개 생성한다.

첫 번째 for문은 m부터 n까지의 수가 소수인지 판별한다.

cnt라는 boolean값을 하나 만들어 일단 True상태로 둔다.

두 번째 for문은 m부터 n까지의 수 하나하나를 2부터 i(현재 수)까지 나누어보고

나누어떨어진다면 소수가 아니므로 cnt값을 False로 변경한다.

어차피 한번 False로 변경된 수는 소수가 아니므로 계속 for문을 반복할필요가 없기에

시간 복잡도를 줄이기 위해 break로 중단한다.

두 번째 for문을 통과했을 때 cnt값이 True라면 그 수는 소수이므로 li에 추가해준다.

위의 for문들은 숫자 1을 배제하지 않았기 때문에, li안에는 1도 포함되어 있을 수 있다.

그래서 조건문으로 li안에 1이 있다면 pop함수를 이용해 0번째값(1은 무조건 0번째)을 제거해준다.

그리고 한 줄에 한 개씩 출력해주면 정답이다.