[BAEKJOON] 백준 1929번: 소수 구하기 (Python)

문제 링크: https://www.acmicpc.net/problem/1929

1929번: 소수 구하기

문제

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

입력

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

출력

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

---

코드 (1차 - 실패)

A, B = map(int, input().split())
for i in range(A, B+1):
    error = 0
    for j in range(2, i):
        if i % j == 0:
            error += 1
    if error == 0:
        print(i)

문제 요약

주어진 숫자 범위 내에 존재하는 소수를 구하는 문제이다.

코드 설명

1. 정말 간단하게 풀고, 나와 같은 코딩 초보자들은 첫 시도는 나와 비슷하게 하지 않을까 생각을 한다.
2. 변수 A, B에 공백으로 구분되는 숫자를 각각 할당 한 뒤, 첫번째 for 문을 통해 A부터 B까지 순회하며, 인자 i는 두 번째 for문으로 전달된다.
   이 때 error 변수를 선언, 소수인지 아닌지 판단하기 위한 변수를 0으로 선언한다.
3. 두 번째 for문에서 인자 i 이전의 숫자로 i를 나눌 경우 나머지가 0인 경우 error의 value를 1 증가시킨다.
4. 두 번째 for문이 끝났을 때 error 변수가 0인 경우, 자기 자신보다 적은 숫자에서 자기 자신을 나눌 수 없으므로 소수가 되므로, 출력한다.

해당 코드로 정답을 제출할 경우, 

자기 자신의 숫자 직전까지 모두 검토해야하므로, 시간 초과가 뜨게 된다.

---

해당 문제에 풀이에 대해 생각해보다 검색을 통해 알게 된 것이 "에라토스테네스의 체"이다.
(출처 : 에라토스테네스의 체, 위키백과)

 

에라토스테네스의 체

에라토스테네스의 체 란?

소수를 판별하는 알고리즘이다.

소수들을 대량으로 빠르고 정확하게 구하는 방법이다.

단일 숫자 소수 여부 확인

어떤 수의 소수의 여부를 확인 할 때는, 특정한 숫자의 제곱근 까지만 약수의 여부를 검증하면 O(N^1/2)의 시간 복잡도로 빠르게 구할 수 있다.

수가 수(N이라고 가정)를 나누면 몫이 생기는데, 몫과 나누는 수 둘 중 하나는 N 제곱근 이하이기 때문이다.

만약, 대량의 소수를 한꺼번에 판별해야할 경우는 '에라토스테네스의 체'를 이용한다.

---

코드

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

A, B = map(int, input().split())

for i in range(A, B+1):
    if isPrime(i):
        print(i)

코드 설명

1. 위의 에라토스테네스이 체 방법을 이용하여 숫자의 제곱근 까지만 약수의 여부를 검증하는 함수 isPrime을 생성한다.
2. 1은 소수가 될 수 없기 때문에 False를, 1 초과 숫자들 중 2이상의 특정 숫자의 제곱근 까지 for문을 통해 소수를 검증한다.
3. 만일 특정 숫자가 제곱근 미만의 숫자로 나누었을 때 0 또는, 제곱근이 정수로 존재하는 경우 나머지가 0이 된다면, 소수가 아니므로 False를 반환하고, 나누어지지 않을 경우 True를 반환한다.
   

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

4. A, B 변수를 통해 범위에 해당하는 숫자를 입력받는다.
5. for문을 통해 A부터 B 까지 순회하며 isPrime 함수를 통해 소수를 검증한 뒤, True 인 수 들만 출력한다.
   

   A, B = map(int, input().split())
   
   for i in range(A, B+1):
       if isPrime(i):
           print(i)​