[백준] 기본 수학 2 - 1929번 (Python)

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())

for i in range(m, n+1):
    error = 0
    if i > 1:
        for j in range(2, i):
            if i % j == 0:
                error += 1
        if error == 0:
            print(i)

(2)

def sosu(num):
    if num==1:
        return False
    else:
        for i in range(2, int(num**0.5)+1):
            if num%i == 0:
                return False
        return True

M, N = map(int, input().split())

for i in range(M, N+1):
    if sosu(i):
        print(i)

풀이

이전 소수 구하는 것과 마찬가지로 하면 되겠다 싶어서 (1)번 코드와 같이 짜서 제출을 해봤더니 시간 초과 오류가 발생하였다. 너무나 당황해 인터넷을 서칭해보았더니 (2)번 코드와 같이 하면 된다고 하기에 가져와보았다. 아래는 (2)번 코드에 대한 설명이니 헷갈리지 말자.

 

• 10행 : 숫자 2개를 공백으로 구문하여 받아 각각 m과 n에 대입한다.
• 12행 : m 값부터 n 값까지 i에 선언하며 13~14행을 반복한다.
• 13행 : sosu(i) 를 이용하여 i의 값을 sosu 함수에 대입하여 불러오게 된다.(1행으로 간다)
• 1행 : def sosu(num) 즉, sosu(i)의 값을 가져와 num으로 변형 후 2~8행을 실행한다.
• 2~3행 : num에 저장된 값이 1이라면 False를 리턴한다.
• 4행 : if가 참이 아닐 시 5~8행을 실행한다.
• 5행 : 2부터 num에 저장된 값을 제곱근 시킨 값까지를 i에 선언한다.  제곱근까지의 약수를 구하면 해당 약수를 포함하는 수를 모두 제거할 수 있다고 한다. ex) i = 12에서 12의 약수는 1 2 3 4 6 12가 된다. int(sqrt(12)) = 3이고 12는 3으로 나누어 떨어지므로 더 검사할 필요가 없다고 한다. (나는 잘 모르겠다...)
• 6~7행 : num을 i로 나눈 값의 나머지가 0일 경우 false를 리턴하여 값을 돌려주지 않는다.
• 8행 : 6~7의 값에 충족하지 않아 리턴이 되지 않을 경우 작동된다. True를 반환하여 num에 저장된 값을 반환한다.